《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》動(dòng)態(tài)單鏈表的實(shí)現(xiàn)
清華大學(xué)計(jì)算機(jī)系列教材? ?累計(jì)發(fā)行超400萬(wàn)冊(cè)
嚴(yán)蔚敏 吳偉明 編著
數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）
以下是本人對(duì)該紫皮書(shū)第二章線性表中動(dòng)態(tài)單鏈表的代碼實(shí)現(xiàn)，函數(shù)部分與課本基本相同，并額外補(bǔ)充了一點(diǎn)代碼
（貌似專(zhuān)欄把我縮進(jìn)吃了，懶得加了，建議用visual studio編譯）
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode, * LinkList;
/*
關(guān)于一個(gè)帶*號(hào)一個(gè)不帶的解釋?zhuān)?/p>
typedef struct LNode LNode;? ? ? ? ?//將結(jié)構(gòu)體類(lèi)型struct LNode重命名為L(zhǎng)Node
typedef struct LNode *LinkList;? ? ?//將struct LNode *重命名為L(zhǎng)inkList
LinkList L;? ? //等價(jià)于 struct LNode * L
可以理解為，通過(guò)typedef，將struct LNode *替換為L(zhǎng)inkList,當(dāng)我們?cè)谑褂肔inkList L定義變量時(shí),
實(shí)際上就是在使用 struct LNode * L定義變量。使得以后想定義指向struct LNode類(lèi)型的指針變量時(shí)，
不需要寫(xiě)struct LNode * ,只需要使用LinkList，減少了代碼的書(shū)寫(xiě)。
*/
/*
重要操作：
p = L; ? ? ?//p指向頭結(jié)點(diǎn)
s = L->next; //s指向首元結(jié)點(diǎn)
p = p->next; //p指向下一結(jié)點(diǎn)
*/
Status InitList(LinkList& L);//鏈表初始化
Status ListInsert_L(LinkList& L, int i, ElemType e);//在第i個(gè)位置之前插入元素e
int ListEmpty(LinkList L);//判斷鏈表是否為空
int ListLength_L(LinkList L);//求線性表表長(zhǎng)
Status GetElem_L(LinkList L, int i, ElemType& e);//按位查找第i個(gè)元素是什么
int LocateElem_L_Value(LinkList L, ElemType e);//按值查找值為e的元素并返回其位置
void Output(LinkList L);//打印線性鏈表中所有元素
Status ListDelete_L(LinkList& L, int i, ElemType& e);//刪除第i個(gè)元素并由e返回其值
Status ClearList(LinkList& L);//清空單鏈表
Status DestoryList_L(LinkList& L);//銷(xiāo)毀單鏈表
void CreatList_H(LinkList& L, int n);//用頭插法快速建立鏈表
void CreatList_R(LinkList& L, int n);//尾插法快速建立鏈表
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc);//已知單鏈線性表La和Lb的元素按值遞增排列，歸并得遞增排列的Lc
void Menu()
{
printf("***************************\n");
printf("********開(kāi) 始 菜 單********\n");
printf("********0：退出系統(tǒng)********\n");
printf("********1：插入元素********\n");
printf("********2：判斷空表********\n");
printf("********3：計(jì)算表長(zhǎng)********\n");
printf("********4：按位查找********\n");
printf("********5：按值查找********\n");
printf("********6：打印表單********\n");
printf("********7：刪除元素********\n");
printf("********8：清空鏈表********\n");
printf("********9：銷(xiāo)毀鏈表********\n");
printf("********10：頭插法*********\n");
printf("********11：尾插法*********\n");
printf("********12：合并表*********\n");
printf("********13：清? 屏*********\n");
printf("***************************\n");
}
int main()
{
int input = 0;
int ret = 0;
int value = 0;
int position = 0;
int Length = 0;
int num = 0;
LinkList head;
InitList(head);
do
{
Menu();
printf("請(qǐng)輸入你想使用的功能：");
scanf("%d", &input);
switch (input)
{
case 1:
printf("請(qǐng)輸入你想插入的元素：");
scanf("%d", &value);
printf("請(qǐng)輸入你想插入的位置：");
scanf("%d", &position);
ret = ListInsert_L(head, position, value);
if (!ret)
{
printf("插入失敗，請(qǐng)重試\n");
}
else
{
printf("插入成功！\n");
}
break;
case 2:
if (ListEmpty(head))
{
printf("該鏈表為空表\n");
}
else
{
printf("該鏈表不是空表\n");
}
break;
case 3:
Length = ListLength_L(head);
printf("該鏈表的長(zhǎng)度為：%d\n", Length);
break;
case 4:
printf("請(qǐng)輸入你想查找的位置：");
scanf("%d", &position);
if (GetElem_L(head, position, value))
{
printf("第%d位的元素為%d\n", position, value);
}
else
{
printf("您輸入的位置不合法\n");
}
break;
case 5:
printf("請(qǐng)輸入你想查找的值：");
scanf("%d", &value);
position = LocateElem_L_Value(head, value);
if (position)
{
printf("你想查找的元素%d第一次出現(xiàn)在第%d位\n", value, position);
}
else
{
printf("未找到\n");
}
break;
case 6:
Output(head);
break;
case 7:
printf("請(qǐng)輸入你想刪除的位置：");
scanf("%d", &position);
if (ListDelete_L(head, position, value))
{
printf("你成功刪除了第%d個(gè)元素%d\n", position, value);
}
else
{
printf("刪除失敗，請(qǐng)重試\n");
}
break;
case 8:
if (ClearList(head))
{
printf("清空鏈表成功\n");
}
else
{
printf("清空失敗，請(qǐng)重試\n");
}
break;
case 9:
printf("您真的要銷(xiāo)毀鏈表嗎？\n1：確認(rèn)\t0：取消\n");
scanf("%d", &ret);
if (ret == 1)
{
if (DestoryList_L(head))
{
printf("銷(xiāo)毀成功\n");
}
else
{
printf("銷(xiāo)毀失敗\n");
}
}
else
{
printf("取消銷(xiāo)毀\n");
}
break;
case 10:
//此時(shí)使用頭插法會(huì)清空之前插入的鏈表
printf("請(qǐng)輸入你想插入的元素個(gè)數(shù)：");
scanf("%d", &num);
CreatList_H(head, num);
printf("插入成功\n");
break;
case 11:
//此時(shí)使用尾插法會(huì)清空之前插入的鏈表
printf("請(qǐng)輸入你想插入的元素個(gè)數(shù)：");
scanf("%d", &num);
CreatList_R(head, num);
printf("插入成功\n");
break;
case 12:
printf("使用尾插法建立兩個(gè)遞增鏈表:\n");
printf("請(qǐng)輸入你想新建的鏈表1元素個(gè)數(shù)：");
scanf("%d", &num);
LinkList head1;
InitList(head1);
CreatList_R(head1, num);
printf("請(qǐng)輸入你想新建的鏈表2的元素個(gè)數(shù)：");
scanf("%d", &num);
LinkList head2;
InitList(head2);
CreatList_R(head2, num);
LinkList head3;
InitList(head3);
MergeList_L(head1, head2, head3);
printf("合并后的鏈表：");
Output(head3);
break;
case 13:
system("cls");
break;
case 0:
exit(0);
break;
default:
printf("輸入有誤，請(qǐng)重新輸入\n");
break;
}
} while (1);
return 0;
}
Status InitList(LinkList& L)//鏈表初始化
{
L = (LinkList)malloc(sizeof(LNode));
if (!L)
{
exit(OVERFLOW);
}
L->next = NULL;
return OK;
}
Status ListInsert_L(LinkList& L, int i, ElemType e)//在第i個(gè)位置之前插入元素e
{
LinkList p = L;
int j = 0;
while (p && j < i - 1)//注意是i-1,因?yàn)橐冶徊迦朐氐那耙粋€(gè)元素
{
p = p->next;
j++;
}
if (!p || j > i - 1)
{
return ERROR;
}
LinkList s = (LinkList)malloc(sizeof(LNode));
if (!s)
{
exit(OVERFLOW);
}
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
int ListEmpty(LinkList L)//判斷鏈表是否為空
//空表：頭指針和頭結(jié)點(diǎn)仍然存在，但頭結(jié)點(diǎn)指向NULL
{
if (L->next)
{
return 0;
}
else
{
return 1;
}
}
int ListLength_L(LinkList L)//求線性表表長(zhǎng)
{
LNode* p;
p = L->next;
int i = 0;
while (p)
{
i++;
p = p->next;
}
return i;
}
Status GetElem_L(LinkList L, int i, ElemType& e)//查找第i個(gè)元素是什么
{
LinkList p = L->next;
int j = 1;
while (p && j < i)
{
p = p->next;
j++;
}
if (!p || j > i)
{
return ERROR;//表示第i個(gè)元素不存在
}
e = p->data;
return OK;
}
int LocateElem_L_Value(LinkList L, ElemType e)//按值查找值為e的元素并返回其位置
//查找失敗返回NULL
{
LNode* p = L->next;
int j = 1;
while (p && p->data != e)
{
p = p->next;
j++;
}
if (p)
{
return j;
}
else
{
return 0;
}
}
void Output(LinkList L)//打印線性鏈表中所有元素
{
if (L->next == NULL)
{
printf("該鏈表為空表\n");
return;
}
LNode* p = L->next;
while (p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
Status ListDelete_L(LinkList& L, int i, ElemType& e)//刪除第i個(gè)元素并由e返回其值
{
LinkList p = L;
int j = 0;
while (p->next && j < i - 1)//注意刪除是p->next，插入是p
{
p = p->next;
j++;
}
if (!(p->next) || j > i - 1)
{
return ERROR;
}
LinkList q = p->next;//注意刪除要先定義一個(gè)指針記錄被刪除的元素，再把指針free掉
p->next = q->next;
e = q->data;//用e來(lái)保存被刪除的元素
free(q);
return OK;
}
Status ClearList(LinkList& L)//清空單鏈表
//清空保留頭指針、頭結(jié)點(diǎn)
{
LNode* p, * q;
p = L->next;
while (p)
{
q = p->next;
free(p);
p = q;
}
L->next = NULL;
return OK;
}
Status DestoryList_L(LinkList& L)//銷(xiāo)毀單鏈表
//銷(xiāo)毀包括頭指針、頭結(jié)點(diǎn)
{
LNode* p;
while (L)
{
p = L;
L = L->next;
free(p);
}
return OK;
}
void CreatList_H(LinkList& L, int n)//用頭插法快速建立鏈表
{
L = (LinkList)malloc(sizeof(LNode));
if (!L)
{
exit(OVERFLOW);
}
L->next = NULL;
for (int i = n; i > 0; i--)//倒序插入
{
LNode* p = (LinkList)malloc(sizeof(LNode));
if (!p)
{
exit(OVERFLOW);
}
scanf("%d", &p->data);
p->next = L->next;
L->next = p;
}
}
void CreatList_R(LinkList& L, int n)//尾插法快速建立鏈表
{
L = (LinkList)malloc(sizeof(LNode));
if (!L)
{
exit(OVERFLOW);
}
L->next = NULL;
LNode* r = L;//尾指針
for (int i = 0; i < n; i++)
{
LNode* p = (LinkList)malloc(sizeof(LNode));
if (!p)
{
exit(OVERFLOW);
}
p->next = NULL;
scanf("%d", &p->data);
r->next = p;//插入到表尾
r = p;//尾指針指向新的尾結(jié)點(diǎn)
}
}
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc)//已知單鏈線性表La和Lb的元素按值遞增排列，歸并得遞增排列的Lc
{
LNode* pa = La->next;
LNode* pb = Lb->next;
LNode* pc = La;
Lc = pc;
while (pa && pb)
{
if (pa->data <= pb->data)
{
pc->next = pa;
pc = pa;//指針后移
pa = pa->next;
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;
free(Lb);
}
