鏈表演算法必備

A. 求幾個有關鏈表的最基本演算法

這個也太多了！
1.循環單鏈表,且含有頭結點的
p = head->next;
for(len=0；p->next!=head；p=p->next)
{
len++ //長度加1
}
2.插入
Status ListInsert(DuLinkList L, int i, ElemType e)
{
DuLinkList p, s;
//i值不合法
if(i < 1 || i > ListLength(L) + 1) return ERROR;

//在L中確定第i個元素前驅的位置指針p
p = GetElemP(L, i - 1);

//p=NULL,即第i個元素的前驅不存在(設頭結點為第1個元素的前驅)
if(!p) return ERROR;

//給插入的數據分配空間
s = (DuLinkList)malloc(sizeof(DuLNode));

//如果為空，分配失敗
if(!s) return OVERFLOW;

//在第i-1個元素之後插入
s->data = e;
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;

return OK;
}
刪除
Status ListDelete(DuLinkList L,int i,ElemType *e)
{
DuLinkList p;

// i值不合法
if(i < 1) return ERROR;

// 在L中確定第i個元素的位置指針p
p = GetElemP(L, i);

// p=NULL,即第i個元素不存在
if(!p) return ERROR;
*e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}
3.帶有頭結點
p=head->next;
head->next =NULL;
q= head;
while(p)
{
q->next = p;
q = p;
p=p->next
}
4.帶頭結點
p=head->next;
head->next = head;
q = head;
while(p!=head)
{
if(head->next = head){q->next=p;q->next = head;}
else{q->next = p;}
q = p;
}
5.帶頭結點
p = head->next;
p->prior = NULL;
q = head;
while(p)
{
q->prior = p;
q->next = p->next;
p->next->prior = q;
p->next = q;

}

B. 用C語言實現鏈表的演算法

這個是我們數據結構上機實驗的鏈表問題，

#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(LinkNode)
typedef int Datatype;
typedef int Status;
typedef struct LinkNode{
Datatype data;
struct LinkNode *next;
} LinkNode,*LinkList;
typedef struct OrderedList
{
LinkNode *head,*tail;
int Listsize;
} OrderedList;//有序循環鏈表的頭節點head,尾接接節點 tail及長度Listsize
Status InitList(OrderedList *List)//生成循環鏈表頭節點
{
List->tail=List->head=(LinkList)malloc(LEN);
if(List->head==NULL)
return 0;
else
{
List->head->next=List->tail;
List->tail->next=List->head;
List->Listsize=0;

return 1;
}
}
void OrderedInsert(OrderedList *List,Datatype data)//每調用一次有序插入data形成有序的(從小到大)的鏈表

{ LinkNode *p ,*q;

if(List->head==List->tail->next)
{
p=(LinkNode*)malloc(LEN);
p->data = data;
List->head->next=p;
p->next=List->tail;
List->Listsize++;
}
else
{
p=List->head->next;
q = List->head;
while(p->data<data&&p!=List->tail)
{
q = p;
p=p->next;
}
if(p->data==data)
{printf("YOu have input the same datas %d\n\t YOu should input another data \n",data);
scanf("%d",&data);
OrderedInsert(List,data);
}
else
{
p=(LinkNode*)malloc(LEN);
p->data = data;
p->next = q->next;
q->next = p;
List->Listsize++;
}
}
}
void Creatset(OrderedList *List)//多次調用OrderedInsert()生成有序鏈表即集合List
{
Datatype data;
int setsize , i=0;
printf("Please input the setsize you want to creat:\n");
scanf("%d",&setsize);
InitList(List);
if(setsize==0)
printf("You needen't input any data\n");
else if(setsize==1)
printf("Please input a single data\n");
else
printf("Please input %d different datas;\n",setsize);
while(i<setsize||setsize>List->Listsize)//當循環次數i小於setsize或者集合內實際元素數List.Listsize小於setsize時一直循環下去
{
scanf("%d",&data);
OrderedInsert(List,data);
i++;
}
}

void Append(OrderedList *List,Datatype data)//在循環鏈表的最後面追加 一個data
{
LinkNode *p;
p=(LinkNode*)malloc(LEN);
p->data=data;
List->tail=List->tail->next=p;
List->tail->next=List->head;
List->Listsize+=1;
}
void MergeList(OrderedList La,OrderedList Lb,OrderedList *Lc)//有序循環鏈表ListLa,ListLb求並集生成ListLc
{
LinkList Pa,Pb;
Pa=La.head->next;Pb=Lb.head->next;
while(Pa!=La.tail&&Pb!=Lb.tail)
{
if(Pa->data<=Pb->data)
{
Append(Lc,Pa->data);
Pa=Pa->next;
}

else {
Append(Lc,Pb->data);Pb=Pb->next;
}
}
while(Pa!=La.tail)
{ Append( Lc,Pa->data);Pa=Pa->next;}

while(Pb!=Lb.tail)
{ Append(Lc,Pb->data);Pb=Pb->next;}

}
void Print(OrderedList List)
{
LinkNode *p;
p=List.head->next;
if(p->next==List.head)
printf("No Elem\n");
while(p!=List.head)
{ printf("%5d",p->data);p=p->next; }
printf("\n");
}
void main()
{
OrderedList ListLa,ListLb,ListLc;
Creatset(&ListLa);
Creatset(&ListLb);
InitList(&ListLc);
MergeList(ListLa,ListLb,&ListLc);
printf("The orgnial list ListLa,ListLb:\n");
Print(ListLa);
Print(ListLb);
printf("The Merge list ListLc;\n");
Print(ListLc);
}

C. 編寫鏈表演算法

直接利用兩個指針，指向兩個節點，p1
p2，p1指向兩者較大的，最後p1所指向的就是
表中值最大的節點：
typedef
struct
node
{
int
elem;
struct
node*
next;
}node;
//*****************初始化表*******************
void
initlink(node*
&l)
{
l
=
new
node;
l->next
=
null;
}
//*****************創建表**********************
void
creatlink(node*
l)
{
cout<<"請輸入表數據，以-1結束輸入:"<
>s->elem,s->elem
!=
-1)
{
s->next
=
null;
p->next
=
s;
p
=
s;
s
=
new
node;
}
delete
s;
}
//*****************列印表************************
void
print(node*
l)
{
node*
p
=
l->next;
while(p)
{
cout<
elem<<"
";
p
=
p->next;
}
cout<
next;
p2
=
p1->next;
while(p2)
{
if(p2->elem
>
p1->elem)
{
p1
=
p2;
p2
=
p2->next;
}
else
{
p2
=
p2->next;
}
}
return
p1;
}
int
main()
{
node*
l;
initlink(l);
creatlink(l);
cout<<"鏈表為:";
print(l);
node*
p
=
searchmax(l);
cout<<"表中最大值為:";
cout<
elem<
評論
0
0
載入更多