单链表的基本操作及C语言代码实现 |
您所在的位置:网站首页 › c语言如何导出文件字符内容并转为链表并返回头指针 › 单链表的基本操作及C语言代码实现 |
(续接前文) 1. 遍历单链表(打印,修改)便利的概念想必大家都不会陌生,即就是从链表的头开始,逐步向后进行每一个元素的访问,这就是遍历,对于遍历操作,我们可以衍生出很多常用的数据操作,比如说查询元素,修改元素,获取元素个数,打印整个链表数据等等。 进行遍历的思路极其简单,只需要建立一个指向链表L的结点,然后沿着链表L逐个向后搜索即可。 对于遍历操作,以下是代码实现: //便利输出单链表 void printList(LinkedList L){ Node *p=L->next; int i=0; while(p){ printf("第%d个元素的值为:%d\n",++i,p->data); p=p->next; } }对于元素修改操作,以下是代码实现: //链表内容的修改,再链表中修改值为x的元素变为为k。 LinkedList LinkedListReplace(LinkedList L,int x,int k) { Node *p=L->next; int i=0; while(p){ if(p->data==x){ p->data=k; } p=p->next; } return L; }简单的遍历设计的函数只需要void无参即可,而当我们需要进行元素修等涉及到元素操作时,我们可以设计一个LinkedList类型的函数,使其返回一个修改后的新链表。 以上的操作均用到了遍历的思维,针对于遍历还有非常多的用法供自主设计,请参考后文配套的习题进行练习。 2. 链表插入操作链表的增加结点操作主要分为查找到第i个位置,将该位置的next指针修改为指向我们新插入的结点,而新插入的结点next指针指向我们i+1个位置的结点。其操作方式可以设置一个前驱结点,利用循环找到第i个位置,再进行插入。 如图,在DATA1和DATA2数据结点之中插入一个NEW_DATA数据结点: 从原来的链表状态 到新的链表状态: 以下是代码实现: //单链表的插入,在链表的第i个位置插入x的元素 LinkedList LinkedListInsert(LinkedList L,int i,int x) { Node *pre; //pre为前驱结点 pre = L; int tempi = 0; for (tempi = 1; tempi next; //查找第i个位置的前驱结点 } Node *p; //插入的结点为p p = (Node *)malloc(sizeof(Node)); p->data = x; p->next = pre->next; pre->next = p; return L; }3. 链表删除操作删除元素要建立一个前驱结点和一个当前结点,当找到了我们需要删除的数据时,直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点,再将原有的结点通过free函数释放掉。 参考如图 以下是代码实现: //单链表的删除,在链表中删除值为x的元素 LinkedList LinkedListDelete(LinkedList L,int x) { Node *p,*pre; //pre为前驱结点,p为查找的结点。 p = L->next; while(p->data != x) { //查找值为x的元素 pre = p; p = p->next; } pre->next = p->next; //删除操作,将其前驱next指向其后继。 free(p); return L; }4. 完整实现代码 #include #include //定义结点类型 typedef struct Node { int data; //数据类型,你可以把int型的data换成任意数据类型,包括结构体struct等复合类型 struct Node *next; //单链表的指针域 } Node,*LinkedList; //单链表的初始化 LinkedList LinkedListInit() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请结点空间 if(L==NULL){ //判断申请空间是否失败 exit(0); //如果失败则退出程序 } L->next = NULL; //将next设置为NULL,初始长度为0的单链表 return L; } //单链表的建立1,头插法建立单链表 LinkedList LinkedListCreatH() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表 int x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF) { Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->NULL L->next = p; } return L; } //单链表的建立2,尾插法建立单链表 LinkedList LinkedListCreatT() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表 Node *r; r = L; //r始终指向终端结点,开始时指向头结点 int x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF) { Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 r->next = p; //将结点插入到表头L-->|1|-->|2|-->NULL r = p; } r->next = NULL; return L; } //单链表的插入,在链表的第i个位置插入x的元素 LinkedList LinkedListInsert(LinkedList L,int i,int x) { Node *pre; //pre为前驱结点 pre = L; int tempi = 0; for (tempi = 1; tempi next; //查找第i个位置的前驱结点 } Node *p; //插入的结点为p p = (Node *)malloc(sizeof(Node)); p->data = x; p->next = pre->next; pre->next = p; return L; } //单链表的删除,在链表中删除值为x的元素 LinkedList LinkedListDelete(LinkedList L,int x) { Node *p,*pre; //pre为前驱结点,p为查找的结点。 p = L->next; while(p->data != x) { //查找值为x的元素 pre = p; p = p->next; } pre->next = p->next; //删除操作,将其前驱next指向其后继。 free(p); return L; } //链表内容的修改,再链表中修改值为x的元素变为为k。 LinkedList LinkedListReplace(LinkedList L,int x,int k) { Node *p=L->next; int i=0; while(p){ if(p->data==x){ p->data=k; } p=p->next; } return L; } //便利输出单链表 void printList(LinkedList L){ Node *p=L->next; int i=0; while(p){ printf("第%d个元素的值为:%d\n",++i,p->data); p=p->next; } } int main() { //创建 LinkedList list; printf("请输入单链表的数据:以EOF结尾\n"); list = LinkedListCreatT(); //list=LinkedListCreatT(); printList(list); //插入 int i; int x; printf("请输入插入数据的位置:"); scanf("%d",&i); printf("请输入插入数据的值:"); scanf("%d",&x); LinkedListInsert(list,i,x); printList(list); //修改 printf("请输入修改的数据:"); scanf("%d",&i); printf("请输入修改后的值:"); scanf("%d",&x); LinkedListReplace(list,i,x); printList(list); //删除 printf("请输入要删除的元素的值:"); scanf("%d",&x); LinkedListDelete(list,x); printList(list); return 0; }5. 配套练习推荐1676题、1052题 请独自完成提交并通过 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |