数据结构单链表的基本操作的实现-阿南达文事网

数据结构单链表的基本操作的实现

文章目录

- - - 一、实验目的
    - 二、实验内容
    - 三、问题分析
    - 四、算法设计
    - - 4.1、插入一个新元素到第i个位置算法思路
      - 4.2、删除第i个位置的元素算法思路
      - 4.3、显示线性表中所有元素的值算法思路
      - 4.4、检索表中第i个元素算法思路
      - 4.5、求表的长度算法思路
    - 五、程序界面
    - 六、总结
    - 七、代码

一、实验目的

(1)掌握线性表的链接存储结构；
(2)验证链接表及其基本操作的实现；
(3)掌握数据结构及算法的程序实现的基本方法。

二、实验内容

在线性表中实现如下操作：
(1)插入一个新元素到第i个位置。
(2)删除第i个位置的元素。
(3)显示线性表中所有元素的值。
(4)检索表中第i个元素。
(5)求表的长度。
要求：请用链表实现，设计菜单，根据菜单提示进行操作。

三、问题分析

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素。用单链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。单链表是一种动态结构，对于每个链表来捉，它所占用的空间大小和位置是不需要预先分配的。所以创建单链表的过程，先初始化单链表，即从“空表”的初始状态，依次建立各元素结点，并插入到链表中。那么创建整个单链表有两种方法：头插法和尾插法，有了非空的单链表后就可以进行其余的操作。

四、算法设计

4.1、插入一个新元素到第i个位置算法思路

①声明一个指针p指向链表的第一个结点，初始化j从0开始；
②当j<i-1时，遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
③若到链表末尾p为空，说明第i个元素不存在，否则查找成功，在系统中生成一个空结点q；
④将数据元素e赋值给q->data；
⑤将q结点插入到链表中，q->next=p->next;p->next=q;
⑥返回成功。

//插入元素
int ListInsert(LinkList &L,int i, ElemType e){LinkList p = L, q;int j = 0;while(p && j < i - 1){//寻找第i-1个结点p = p ->next;j++;}if(!p || i < 1)return ERROR;//i大于表长+1或小于1q = new LNode;  //生成新结点qq -> data = e;  //将结点q 的数据域置为eq -> next = p -> next;//将结点q 插入L中p -> next = q;return OK;
}

4.2、删除第i个位置的元素算法思路

①声明一个指针p指向链表的第一个结点，初始化j从0开始;
②当j<i-1时，遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
③若到链表末尾p为空，说明第i个元素不存在，否则查找成功，将预删除的结点p->next赋值给q；
④执行删除标准语句p->next = q->next;
⑤将q结点中的数据赋值给e,作为返回;
⑥释放q结点，返回成功。

//删除元素
int ListDelete(LinkList &L,int i, ElemType &e){LinkList p = L,q;int j = 0;while(p -> next && j < i-1){//寻找第i个结点，并令p指向其前驱p = p -> next;j++;}if(!(p -> next) || i < 1)return ERROR;           //删除位置不合理q = p -> next;              //临时保存被删结点的地址以备释放p -> next = q -> next;      //改变被删除结点前驱结点的指针域e = q -> data;              //保存被删除节点的数据域delete q;                   //释放被删除结点的空间return OK;
}

4.3、显示线性表中所有元素的值算法思路

①判断链表L是否为空，若链表为空，则输出“表空！”，并返回；
②声明一个指针p指向链表的第一个结点，当单链表非空时，遍历链表，输出链表的数据，并让p的指针后移，不断指向下一结点。

//显示线性表
void DispList(LinkList L){printf("单链表为：");if(ListEmpty(L)){printf("表空！\n");return;}LinkList p = L -> next;while(p){printf("%d ",p -> data);p = p -> next;}printf("\n");
}

4.4、检索表中第i个元素算法思路

①声明一个指针p指向链表的第一个结点，初始化j从1开始;
②当j<i时,遍历链表,让p的指针向后移动，不断指向下一结点, j累加1;
③若到链表末尾p为空,说明第i个元素不存在;
④否则查找成功，返回结点p的数据。

//检索元素
int GetElem(LinkList L,int i,ElemType &e){LinkList p = L->next;int j = 1;while(p != NULL && j < i){p = p ->next;j++;}if (!p || i < 1)return ERROR;e = p->data;return OK;
}

4.5、求表的长度算法思路

①声明一个指针p指向链表的第一个结点，初始化i从0开始;
②若链表非空，遍历链表, i累加1，让p的指针向后移动，不断指向下一结点;
③返回统计节点数i的值。

//求表长
int LengthList(LinkList L){LinkList p = L -> next;//p指向第一个结点int i = 0;while(p){i++;p = p->next;}return i;
}

五、程序界面

主菜单界面，可实现13种操作

六、总结

该程序所包含的内容有线性表的初始化、创建、元素插入、删除元素、查找元素和长度统计，具体操作根据屏幕提示进行。最后以“0”的输入来结束程序!
当要在单链表的第i个位置插入一个元素时，必须先将单链表第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。当要删除第i个元素时，也只需将地i个元素之后的所有元素前移一个位置。以及遍历链表时逐一遍历，指针结点后移。程序的时间和空间效率均为O(n)。
通过对该程序的调试与运行，使得对线性表的功能及其构成有了进一步的了解! 一个完整的程序，是由许多模块所组成的，要使程序能正常运行，必须使每个功能都能正常运行，且能相互连接。就像一个建筑，需要有许多结构组成，任何一个结构都不能有差错！

七、代码

最后呈现一下全部代码

#include<stdio.h>
#define OK 1
#define ERROR 0
#define ListSize 100
typedef int ElemType;
typedef struct Node{ElemType data;struct Node *next;
}LNode,*LinkList;//构造一个空的单链表L,初始化
int IniList(LinkList &L){L = new LNode;//为头结点分配存储单元if(!L)return ERROR;//无足够的内存空间，初始化失败L -> next = NULL;return OK;
}//销毁链表
int DestoyList(LinkList &L){LinkList p;while (L){p = L;L = L->next;delete p;}return OK;
}//将L重置为空表
void ClearList(LinkList &L){LinkList p,q;p = L->next;//p指向第一个结点while(p){   //没到表尾q = p ->next;delete p;p = q;}L -> next = NULL;//头指针指针域为空
}//返回L中数据元素个数
int LengthList(LinkList L){LinkList p = L -> next;//p指向第一个结点int i = 0;while(p){i++;p = p->next;}return i;
}//若L为空表，则返回true, 否则返回false
int ListEmpty(LinkList L){if(L->next == NULL)return true;elsereturn false;
}LinkList LocateElem(LinkList L,ElemType e){LinkList p;p = L->next;while(p && p->data != e)p = p ->next;return p;//返回L中值为e的数据元素的位置，查找失败返回NULL
}//在带头结点的单链表L中查找第i各元素
int GetElem(LinkList L,int i,ElemType &e){LinkList p = L->next;int j = 1;while(p != NULL && j < i){p = p ->next;j++;}if (!p || i < 1)return ERROR;e = p->data;return OK;
}//将值为e的新结点插入到表的第i个结点的位置上
int ListInsert(LinkList &L,int i, ElemType e){LinkList p = L, q;int j = 0;while(p && j < i - 1){//寻找第i-1个结点p = p ->next;j++;}if(!p || i < 1)return ERROR;//i大于表长+1或小于1q = new LNode;  //生成新结点qq -> data = e;  //将结点q 的数据域置为eq -> next = p -> next;//将结点q 插入L中p -> next = q;return OK;
}//按序号删除结点
int ListDelete(LinkList &L,int i, ElemType &e){LinkList p = L,q;int j = 0;while(p -> next && j < i-1){//寻找第i个结点，并令p指向其前驱p = p -> next;j++;}if(!(p -> next) || i < 1)return ERROR;           //删除位置不合理q = p -> next;              //临时保存被删结点的地址以备释放p -> next = q -> next;      //改变被删除结点前驱结点的指针域e = q -> data;              //保存被删除节点的数据域delete q;                   //释放被删除结点的空间return OK;
}//按值删除结点
int ListDeleteValue(LinkList &L,ElemType e){LinkList p = L,q = L -> next;while(q && q -> data != e){ //寻找元素值等于e的结点，并令p指向其前驱p = q;q = q -> next;}if (!q)return ERROR;           //没有找到值为e的结点p -> next = q -> next;      //改变被删除节点的前驱结点的指针域delete q;                   //释放被删除结点的空间return OK;
}//在单链表的头部插入结点建立单链表
void CreateList_F(LinkList &L,int n){//逆位序输入n个元素的值，建立单链表L//要求，在用前插法创建单链表之前，需要执行InitList()初始化单链表，//即先建立一个带表头结点的空表LinkList p;printf("请按逆序依次输入元素的值：");for(int i = n ; i > 0; i--){p = new LNode;          //生成新结点scanf("%d",&p -> data); //输入元素值p -> next = L -> next ;L ->next = p;           //插入到表头}
}//在单链表的尾部插入结点建立单链表
void CreateList_R(LinkList &L,int n){//正位序输入n个元素的值，建立带头结点的单链表L//要求，在用前插法创建单链表之前，需要执行IntList()初始化单链表，//即先建立一个带表头结点的空表LinkList p, r = L;printf("请按正序依次输入元素的值：");for(int i = 0;i < n;i++){p = new LNode;         //生成新结点scanf("%d",&p -> data); //输入元素值p -> next = NULL;r -> next = p;          //插入到表尾r = p;                  //r指向新的尾结点}
}//输出线性表
void DispList(LinkList L){printf("单链表为：");if(ListEmpty(L)){printf("表空！\n");return;}LinkList p = L -> next;while(p){printf("%d ",p -> data);p = p -> next;}printf("\n");
}int _flushall(void){
}//显示菜单
void Showmenu(){printf("\n");printf("   --线性表链式存储基本运算演示--  \n");printf("***********************************\n");printf("*    1 ----单链表的初始化         *\n");printf("*    2 ----销毁单链表             *\n");printf("*    3 ----清空单链表             *\n");printf("*    4 ----求单链表的长度         *\n");printf("*    5 ----判断单链表是否为空     *\n");printf("*    6 ----检索表中第i个元素的值  *\n");printf("*    7 ----检索元素值为e的元素    *\n");printf("*    8 ----插入数据元素           *\n");printf("*    9 ----按序号删除数据元素     *\n");printf("*    10----按值删除数据元素       *\n");printf("*    11----按头插法创建单链表     *\n");printf("*    12----按尾插法创建单链表     *\n");printf("*    0 ----退出                   *\n");printf("***********************************\n");printf("请选择菜单号(0--12): ");
}void List(){int choice;ElemType item;int Position;int number;LinkList L;int flag = 0;               //是否创建好了单链表while(choice){Showmenu();_flushall();scanf("%d",&choice);switch(choice){case 1:printf("初始化单链表操作\n");if(IniList(L)){printf("初始化成功！\n");flag = 1;       //标志顺序表的存在}else{printf("初始化失败！\n");}break;case 2:if(flag){           //单链表存在DestoyList(L);flag = 0;       //单链表已删除printf("单链表删除成功! \n");}else {printf("单链表不存在，操作失败! \n");}break;case 3:if(flag){           //单链表存在ClearList(L);printf("单链表清空成功！\n");DispList(L);    //输出线性表}else{printf("单链表不存在，操作失败! \n");}break;case 4:if(flag){           //单链表存在printf("单链表元素个数为 %d \n",LengthList(L));DispList(L);    //输出线性表}else{printf("单链表不存在，操作失败! \n");}break;case 5:if(flag){           //单链表存在printf("单链表%s.\n",ListEmpty(L)?"空":"不空");DispList(L);    //输出线性表}else{printf("单链表不存在，操作失败! \n");}break;case 6:if(flag){           //单链表存在printf("请输入元素的位序号：");scanf("%d",&Position);if(GetElem(L,Position,item)){printf("第%d个元素为：%d\n",Position,item);}else{printf("输入的位序号有误！\n");}DispList(L);}else{printf("单链表不存在，操作失败! \n");}break;case 7:if(flag){           //单链表存在printf("请输入元素的值：");_flushall();scanf("%d",&item);LinkList P = LocateElem(L,item);if(P){printf("该元素找到,地址为 %x ！\n",P);}else{printf("该元素没找到！\n");}DispList(L);    //输出线性表}else{printf("单链表不存在，操作失败! \n");}break;case 8:if(flag){           //单链表存在printf("请输入元素的值：");_flushall();scanf("%d",&item);printf("请输入要插入数据元素的位序号：");scanf("%d",&Position);if(ListInsert(L,Position,item))printf("该元素插入成功！\n");elseprintf("输入的位序号有误！");DispList(L);    //输出线性表}else{printf("单链表不存在，操作失败! \n");}break;case 9:if(flag){           //单链表存在printf("请输入要删除数据元素的位序号：");scanf("%d",&Position);if(ListDelete(L,Position,item)){printf("删除的元素为 %d ！\n",item);}else{printf("输入的位序号有误！");}DispList(L);    //输出线性表}else{printf("单链表不存在，操作失败! \n");}break;case 10:if(flag){           //单链表存在printf("请输入要删除的元素：");_flushall();scanf("%d",&item);if(ListDeleteValue(L,item)){printf("删除的元素为 %d！\n",item);}else{printf("该元素不存在，删除失败！\n");}DispList(L);    //输出线性表}else{printf("单链表不存在，操作失败! \n");}break;case 11:if(flag){           //单链表存在ClearList(L);   //清空单链表printf("按头插法创建单链表\n");printf("请输入要插入元素的个数：");scanf("%d",&number);_flushall();CreateList_F(L,number);DispList(L);    //输出线性表}else{printf("单链表不存在，操作失败! \n");}break;case 12:if(flag){           //单链表存在ClearList(L);   //清空单链表printf("按尾插法创建单链表\n");printf("请输入要插入元素的个数：");scanf("%d",&number);_flushall();CreateList_R(L,number);DispList(L);    //输出线性表}else{printf("单链表不存在，操作失败! \n");}break;case 0:printf("\n\t程序结束！\t\n");DestoyList(L);break;default:printf("\n\t选择错误，请重新输入！\t\n");break;}}
}int main(){List();return 0;
}