链表算法必备

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
加载更多