單鏈表的頭插、尾插、刪除、合并等操作

單鏈表的頭插、尾插、刪除、合并等操作實現(xiàn)代碼如下：

#include<iostream>

using namespace std;

//單鏈表的存儲結(jié)構(gòu)

typedef struct Node

{

int data;

struct Node* next;

}Node,*LinkList;//LinkList為結(jié)構(gòu)指針類型

//初始化單鏈表

void InitList(LinkList *L)

{

*L = (LinkList)malloc(sizeof(Node));//建立頭結(jié)點

(*L)->next = NULL;//建立空的單鏈表L

}

//L是帶頭結(jié)點的空鏈表頭指針，通過鍵盤輸入表中元素值，利用頭插法建單鏈表L

void CreateFromHead(LinkList L)

{

Node *s;

char c;

int flag = 1;

while (flag)//flag初值為1，當(dāng)輸入'$'時，置flag為0，建表結(jié)束

{

c = getchar();

if (c != '$')

{

s = (Node*)malloc(sizeof(Node));//建立新結(jié)點s

s->data = c;

s->next = L->next;//將s結(jié)點插入表頭

L->next = s;

}

else

{

flag = 0;

}

}

}

//L是帶頭結(jié)點的空鏈表頭指針，通過鍵盤輸入表中元素值，利用尾插法建單鏈表L

void CreateFromFail(LinkList L)

{

Node *r,*s;

r=L;//r指針動態(tài)指向鏈表的當(dāng)前表尾，以便做尾插入，其初值指向頭結(jié)點

int flag = 1;

char c;

while (flag)//flag初值為1，當(dāng)輸入'$'時，置flag為0，建表結(jié)束

{

c = getchar();

if (c != '$')

{

s = (Node*)malloc(sizeof(Node));//建立新結(jié)點s

s->data = c;

r->next = s;

r = s;

}

else

{

flag = 0;

r->next = NULL;//將最后一個結(jié)點的next鏈域置為空，表示鏈表結(jié)束 

}

}

}

//在帶頭結(jié)點的單鏈表L中查找第i個結(jié)點，若找到(1<=i<=n),則返回該結(jié)點的存儲位置，否則返回NULL

Node *Get(LinkList L, int i)

{

int j = 0;

Node *p;

if (i <= 0)

{

return NULL;

}

p = L;

while ((p->next != NULL) && (j < i))

{

p = p->next;//掃描下一結(jié)點

j++;//已掃描結(jié)點計數(shù)器

}

if (i == j)

{

return p;//找到了第i個結(jié)點

}

else

{

return NULL;

}

}

//在帶頭結(jié)點的單鏈表L中查找其結(jié)點值等于key的第1個結(jié)點，若找到則返回該結(jié)點的存儲位置p，否則返回NULL

Node *Locate(LinkList L, int key)

{

Node *p;

p = L->next;//從表中第一個結(jié)點開始

while (p!= NULL) //當(dāng)前表未查完

{

if (p->data!=key)

{

p = p->next; 

}

else

{

break;//找到結(jié)點值等于key時退出循環(huán)

}

}

return p;

}

//求帶頭結(jié)點的單鏈表L的長度

int ListLength(LinkList L)

{

Node *p;

p = L->next;

int j = 0;//用來存放單鏈表的長度

while (p != NULL) 

{

p = p->next;

j++;

}

return j;//j為求得的單鏈表的長度

}

//在帶頭結(jié)點的單鏈表L中第i個位置插入值為e的新結(jié)點，n個元素有n+1個插入位置

#define OK 1

#define ERROR 0

void InsList(LinkList L, int i, int e)

{

Node *pre, *s;

int k = 0;

if (i<=0) //判斷插入位置是否合法

{

cout << "插入位置i值不合法！" << endl;

return (ERROR);

}

pre = L;

while (pre != NULL&&k < (i - 1))//表未查完且未查到第i-1個元素時重復(fù)，若找到pre指向第i-1個

{

pre = pre->next;

k = k + 1;

}

if (!pre)//若當(dāng)前位置pre為空表，已找完還未找到第i個，說明插入位置不合理

{

cout << "插入位置不合理！" << endl;

return (ERROR);

}

s = (Node*)malloc(sizeof(Node));//申請一個新結(jié)點s

s->data = e;//值e置入s的數(shù)據(jù)域

s->next = pre->next;//修改指針，完成插入操作

pre->next = s;

return (OK);

}

//在帶頭結(jié)點的單鏈表L中刪除第i個元素，并將刪除的元素保存到變量*e中

void DelList(LinkList L, int i, int *e)

{

Node *pre, *r;

int k = 0;

pre = L;

while (pre->next != NULL&&k < (i - 1))//尋找被刪除結(jié)點i的前驅(qū)結(jié)點i-1，使p指向它

{

pre = pre->next;

k = k + 1;

}

//while循環(huán)是因為pre->next=NULL或i<1而跳出來的，因為pre->next=NULL，沒有找到合法的前驅(qū)位置，說明刪除位置i不合法

if (!(pre->next))

{

cout << "刪除結(jié)點的位置i不合理！" << endl;

return (ERROR);

}

r= pre->next; 

pre->next=r->next;//修改指針，刪除結(jié)點r

*e=r->data ;

free(r);//釋放被刪除結(jié)點所占的內(nèi)存空間

return (OK);

}

//將遞增有序的單鏈表LA和LB，合并成一個遞增有序的單鏈表LC

LinkList MergeLinkList(LinkList LA, LinkList LB)

{

Node *pa, *pb,*r;

LinkList LC;//將Lc初始置為空表，pa和pb分別指向單鏈表LA和LB中的第一個結(jié)點，r初值為LC且r始終指向LC的表尾

pa = LA->next;

pb = LB->next;

LC = LA;

LC->next = NULL;

r = LC;

//當(dāng)兩個表中均未處理完時，比較選擇將較小值結(jié)點插入到新表LC中

while ((pa != NULL) && (pb != NULL))

{

if (pa->data <= pb->data)

{

r->next= pa;

r = pa;//pa變成新的r結(jié)點

pa=pa->next;

}

else

{

r->next = pb;

r = pb;

pb = pb->next;

}

}

if (pa)//當(dāng)表LA有剩余元素時，則將表LA的剩余元素鏈到新表LC表尾

{

r->next = pa;

}

else//否則將表LB的剩余元素鏈到新表LC表尾

{

r->next = pb;

}

free(LB);

return (LC);

}