单链表完整算法

// 包含头文件

#include

#include

#include

// 为结点数据类型和结构体类型起别名

typedefint datatype;

typedefstructLinkNode

{

datatype data; // 数据域 structLinkNode *next; // 指针域存放下一个结点的地址 }LNode,*LinkList;

LinkList L; // 单链表的头指针

// 1.用头插法创建单链表

LinkListCreateListHead(int n)

{

// 创建头结点 LNode *L = (LNode *)malloc(sizeof(LNode)); L->next = NULL; // 设置指针域为空

LinkList p; // p指向新结点 for(inti=n;i>0;i--) // 先插入最后一个结点，插入次序与逻辑次序相反

p->next = L->next; // 让L原来的后继结点成为p的后 // 从键盘输入新结点的值 printf("请输入要插入第%d结点的值:\n",i); scanf("%d", &p->data); { // 生成新结点 p = (LNode *)malloc(sizeof(LNode)); 继结点

}

// 2.用尾插法创建单链表

LinkListCreateListTail(int n)

{ return L; // 返回单链表的头指针 } L->next = p; // p成为L新的后继结点

// 生成头结点

L = (LNode *)malloc(sizeof(LNode));

L->next = NULL;// 设置指针域为空

// p指向新结点，q指向尾结点

LinkList p, q = L;

// 依次在末尾插入n个结点

for(inti=1;i

{

// 生成新结点p

p = (LNode *)malloc(sizeof(LNode));

// 从键盘输入新结点的值

printf("请输入第%d个结点的值：\n", i);

scanf("%d",&p->data);

p ->next = NULL; // 新结点（也是尾结点）的指针域为空

// 把新结点链接到单链表的末尾

q->next = p;

}

} // 让q指向新的尾结点 q = p; return L;// 返回单链表的头指针

// 3.显示单链表中的元素值

voidShowList(LinkList L)

{

LinkList p = L; // 指针p首先指向头结点 while(p->next!=NULL) // 当指针p没有到达尾结点时 { } p = p->next; // 指针后移一个结点 printf("%d\n",p->data); // 输出结点数据域的值 if(L == NULL || L->next==NULL) { } printf("单链表为空。\n"); return;

}

// 4.求单链表的长度（结点的个数）

intGetLength (LinkList L){

}

// 5.按序号查找：在单链表中查找第i个结点

LinkListLocateElemByIndex(LinkList L, inti)

{

if(L==NULL || L->next==NULL) { LinkList p = L; // 指针p先指向头结点，负责后移 int j = 0; // j用来计算到达结点的序号 return n; //返回结点的个数 while(p->next != NULL){// 当指针p没有到达尾结点时 } p=p->next; //指针后挪一个结点 n++; //结点个数+1 LNode *p=L; /*p 先指向头结点*/ int n=0; //n代表除头结点外的结点个数

return NULL;

}

}

// 6.按值查找：在单链表中查找值为e的结点

LinkListLocateElemByData(LinkList L, datatype e)

{ // p指针后移的条件：p不是尾结点，而且jnext!=NULL && jnext; // p指针后移 j++; // j递增 }else{ } return NULL; // 第i个结点不存在，返回NULL

if(L==NULL || L->next==NULL) { printf("单链表为空。\n"); return NULL;

}

}

// 找到值为e的结点 if(p->data == e) { return p; // 返回结点的地址 // p指针后移的条件：p不是尾结点，而且p->data!=e while(p->next!=NULL && p->data!=e) { } p = p->next; // p指针后移 }else{ } return NULL; // 结点不存在，返回NULL

// 7.在单链表的第i个位置插入值为e的结点（在第i-1个结点后面插入新结点）

voidInsertByIndex(LinkList L, inti, datatype e)

{

// 修改指针域的两行代码次序不能颠倒 s->next=p->next; p->next=s; printf("插入结点完成。\n"); //找到了第i-1个结点 if(p!=NULL) { s=(LNode *)malloc(sizeof(LNode)); s->data=e; LNode *s; LNode *p = LocateElemByIndex(L,i-1); }else { printf("单链表为空或插入位置有误。\n");

}

}

// 8.在单链表中值为e的结点之后插入新结点

voidInsertByDataBehind(LinkList L, datatype e) {

// 修改指针域的两行代码次序不能颠倒 s->next = p->next; p->next = s; printf("插入结点完成。\n"); // 从键盘输入新结点的值 printf("请从键盘输入新结点的值:\n"); scanf("%d",&s->data); // 找到值为e的结点 if(p!=NULL) { // 在值为e的结点之后插入新结点 s=(LNode *)malloc(sizeof(LNode)); LNode *s; // s指向新结点，p指向值为e的结点 LNode *p = LocateElemByData(L,e); }else{ } printf("单链表为空或插入位置有误。\n");

}

// 9.在值为e的结点之前插入

voidInsertByDataBefore(LinkListL,datatype e) {

LinkList p=L,q,s; while(p->next !=NULL && p->data !=e) { } if(p->data==e) { s = (LinkList)malloc(sizeof(LNode)); printf("请输入新结点的值："); scanf("%d",&s->data); s->next = p; //s->next=q->next; q->next = s; printf("插入完成。\n"); q = p; p = p->next; }else { } printf("插入失败。\n");

// 10.在单链表中删除第i个结点

voidDeleteByIndex(LinkList L, inti)

{

}

// 11.删除值为e的结点

voidDeleteByData(LinkList L, datatype e) {

LNode *p=L,*q; //p指向值为e的结点 while(p->next!=NULL && p->data!=e) { q=p; //q指向p的前驱结点 p=p->next; LNode *p = LocateElemByIndex(L,i-1); // p指向第i-1个结点 LNode *q = p->next; // q指向第i个结点（待删除结点） if (q!=NULL) { p->next = q->next; free(q); }else{ } printf("单链表为空或删除位置有误。\n");

if (p->data==e) { q->next = p->next; free (p); printf("删除成功。\n"); } else { printf("删除失败。\n");

}

}

// 12 删除值为e结点的后继结点

voidDeleteByDataBehind(LinkList L, datatype e)

{

LNode *q = p->next; // q指向p的后继结点（待删除结点） // p指针后移的条件：p不是尾结点，而且p->data!=e while(p->next!=NULL && p->data!=e) { } p = p->next; // p指针后移 LinkList p = L; //指针p先指向头结点，负责后移

}

//主函数

void main()

{

printf("----------------------------------\n"); printf("| 1 头插法创建单链表 |\n"); printf("| 2 尾插法创建单链表 |\n"); printf("| 3 求单链表长度 |\n"); printf("| 4 显示单链表中的元素 |\n"); printf("| 5 查找第i个结点 |\n"); printf("| 6 查找值为e的结点 |\n"); printf("| 7 在第i个位置插入 |\n"); printf("| 8 在值为e结点之后插入 |\n"); if (q!=NULL) { p->next = q->next; free(q); }else{ } printf("单链表为空或值为e结点不存在。\n");

printf("| 9 在值为e结点之前插入 |\n"); printf("| 10 删除第i个结点 |\n"); printf("| 11 删除值为e的结点 |\n"); printf("| 12 删除值为e结点的后继结点 |\n"); printf("| 0 退出 |\n"); printf("----------------------------------\n");

intnum; //选择操作对应的数字

int count; //要插入元素的个数

int length; //单链表的长度

LinkList p; //存放查找结点的首地址

inti; //要查找元素的序号

datatype e; //要查找元素的值

do {

printf("请输入要选择操作对应的数字：");

scanf("%d", &num);

switch(num) {

case 1://头插法创建单链表

printf("请输入要插入结点的个数：");

scanf("%d",&count);

L = CreateListHead(count);

if (L==NULL){

printf("头插法创建失败。\n");

} break; printf("头插法创建成功。\n"); case 2://尾插法创建单链表 printf("请输入要插入结点的个数："); scanf("%d",&count); L = CreateListTail(count); if (L==NULL){ printf("尾插法创建失败。\n"); }else { } break; printf("尾插法创建成功。\n"); case 3://求单链表的长度 length = GetLength(L); printf("单链表的长度：%d。\n", length); break; case 4://显示单链表中的元素

break; case 5://查找第i个结点 printf("请输入要查找元素的序号(必须大于0):"); scanf("%d",&i); p = LocateElemByIndex(L,i); if (p==NULL) { printf("未找到。\n"); }else{ } break; printf("找到了。\n"); case 6://查找值为e的结点 printf("请输入要查找元素的值:"); scanf("%d",&e); p = LocateElemByData(L,e); if (p==NULL) { printf("未找到。\n");

} break; printf("找到了。\n"); case 7://在第i个位置插入 printf("请输入要插入的位置:\n"); scanf("%d",&i); printf("请输入要插入元素的值:\n"); scanf("%d",&e); InsertByIndex(L, i, e); break; case 8://插入到值为e的结点之后 printf("插入到值为e的结点:请输入结点的值：\n"); scanf("%d",&e); InsertByDataBehind(L,e); break; case 9://插入到值为e的结点之前

printf("插入到值为e的结点之前:请输入结点的值：\n");

case 12:// 删除值为e结点的后继结点 printf("删除值为e结点的后继结点:请输入结点的 case 11://删除值为e的结点 printf("删除值为e的结点:请输入结点的值:\n"); scanf("%d", &e); DeleteByData(L, e); break; case 10://删除第i个结点 printf("请输入要删除元素的位置:\n"); scanf("%d", &i); DeleteByIndex(L, i); break; scanf("%d",&e); InsertByDataBefore(L,e); break; 值:\n");

scanf("%d", &e);

DeleteByDataBehind(L, e);

break;

case 0://退出

exit(0);

default:

printf("您输入的操作数字有误，请重新输入。 break;

}

printf("----------------------------------\n");

}while(1);

} \n");