單鏈表的頭插、尾插、刪除、合并等操作實(shí)現(xiàn)代碼如下：
#include
using namespace std;
//單鏈表的存儲(chǔ)結(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é)點(diǎn)
(*L)->next = NULL;//建立空的單鏈表L
}
//L是帶頭結(jié)點(diǎn)的空鏈表頭指針，通過鍵盤輸入表中元素值，利用頭插法建單鏈表L
void CreateFromHead(LinkList L)
{
Node *s;
char c;
int flag = 1;
while (flag)//flag初值為1，當(dāng)輸入'$'時(shí)，置flag為0，建表結(jié)束
{
c = getchar();
if (c != '$')
{
s = (Node*)malloc(sizeof(Node));//建立新結(jié)點(diǎn)s
s->data = c;
s->next = L->next;//將s結(jié)點(diǎn)插入表頭
L->next = s;
}
else
{
flag = 0;
}
}
}
//L是帶頭結(jié)點(diǎn)的空鏈表頭指針，通過鍵盤輸入表中元素值，利用尾插法建單鏈表L
void CreateFromFail(LinkList L)
{
Node *r,*s;
r=L;//r指針動(dòng)態(tài)指向鏈表的當(dāng)前表尾，以便做尾插入，其初值指向頭結(jié)點(diǎn)
int flag = 1;
char c;
while (flag)//flag初值為1，當(dāng)輸入'$'時(shí)，置flag為0，建表結(jié)束
{
c = getchar();
if (c != '$')
{
s = (Node*)malloc(sizeof(Node));//建立新結(jié)點(diǎn)s
s->data = c;
r->next = s;
r = s;
}
else
{
flag = 0;
r->next = NULL;//將最后一個(gè)結(jié)點(diǎn)的next鏈域置為空，表示鏈表結(jié)束
}
}
}
//在帶頭結(jié)點(diǎn)的單鏈表L中查找第i個(gè)結(jié)點(diǎn)，若找到(1<=i<=n),則返回該結(jié)點(diǎn)的存儲(chǔ)位置，否則返回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é)點(diǎn)
j++;//已掃描結(jié)點(diǎn)計(jì)數(shù)器
}
if (i == j)
{
return p;//找到了第i個(gè)結(jié)點(diǎn)
}
else
{
return NULL;
}
}
//在帶頭結(jié)點(diǎn)的單鏈表L中查找其結(jié)點(diǎn)值等于key的第1個(gè)結(jié)點(diǎn)，若找到則返回該結(jié)點(diǎn)的存儲(chǔ)位置p，否則返回NULL
Node *Locate(LinkList L, int key)
{
Node *p;
p = L->next;//從表中第一個(gè)結(jié)點(diǎn)開始
while (p!= NULL) //當(dāng)前表未查完
{
if (p->data!=key)
{
p = p->next;
}
else
{
break;//找到結(jié)點(diǎn)值等于key時(shí)退出循環(huán)
}
}
return p;
}
//求帶頭結(jié)點(diǎn)的單鏈表L的長度
int ListLength(LinkList L)
{
Node *p;
p = L->next;
int j = 0;//用來存放單鏈表的長度
while (p != NULL)
{
p = p->next;
j++;
}
return j;//j為求得的單鏈表的長度
}
//在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入值為e的新結(jié)點(diǎn)，n個(gè)元素有n+1個(gè)插入位置
#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個(gè)元素時(shí)重復(fù)，若找到pre指向第i-1個(gè)
{
pre = pre->next;
k = k + 1;
}
if (!pre)//若當(dāng)前位置pre為空表，已找完還未找到第i個(gè)，說明插入位置不合理
{
cout << "插入位置不合理！" << endl;
return (ERROR);
}
s = (Node*)malloc(sizeof(Node));//申請(qǐng)一個(gè)新結(jié)點(diǎn)s
s->data = e;//值e置入s的數(shù)據(jù)域
s->next = pre->next;//修改指針，完成插入操作
pre->next = s;
return (OK);
}
//在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素，并將刪除的元素保存到變量*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é)點(diǎn)i的前驅(qū)結(jié)點(diǎn)i-1，使p指向它
{
pre = pre->next;
k = k + 1;
}
//while循環(huán)是因?yàn)閜re->next=NULL或i<1而跳出來的，因?yàn)閜re->next=NULL，沒有找到合法的前驅(qū)位置，說明刪除位置i不合法
if (!(pre->next))
{
cout << "刪除結(jié)點(diǎn)的位置i不合理！" << endl;
return (ERROR);
}
r= pre->next;
pre->next=r->next;//修改指針，刪除結(jié)點(diǎn)r
*e=r->data ;
free(r);//釋放被刪除結(jié)點(diǎn)所占的內(nèi)存空間
return (OK);
}
//將遞增有序的單鏈表LA和LB，合并成一個(gè)遞增有序的單鏈表LC
LinkList MergeLinkList(LinkList LA, LinkList LB)
{
Node *pa, *pb,*r;
LinkList LC;//將Lc初始置為空表，pa和pb分別指向單鏈表LA和LB中的第一個(gè)結(jié)點(diǎn)，r初值為LC且r始終指向LC的表尾
pa = LA->next;
pb = LB->next;
LC = LA;
LC->next = NULL;
r = LC;
//當(dāng)兩個(gè)表中均未處理完時(shí)，比較選擇將較小值結(jié)點(diǎn)插入到新表LC中
while ((pa != NULL) && (pb != NULL))
{
if (pa->data <= pb->data)
{
r->next= pa;
r = pa;//pa變成新的r結(jié)點(diǎn)
pa=pa->next;
}
else
{
r->next = pb;
r = pb;
pb = pb->next;
}
}
if (pa)//當(dāng)表LA有剩余元素時(shí)，則將表LA的剩余元素鏈到新表LC表尾
{
r->next = pa;
}
else//否則將表LB的剩余元素鏈到新表LC表尾
{
r->next = pb;
}
free(LB);
return (LC);
}
創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。
重慶分公司
重慶分公司
