当前位置：文档之家 › 单链表的基本操作

单链表的基本操作

  • 格式：wps
  • 大小：26.00 KB
  • 文档页数：6

#include <stdio.h>#include <stdlib.h>#define error 0typedef struct str //定义结构踢{int data;struct str *next;} londe,*linklist;void print(linklist &L); //打印出链表linklist create() //创建一个空表{linklist p;p=(linklist)malloc(sizeof(londe));p->next=NULL;return p;}void createlist(linklist &L) //创建链表{linklist p,r;int n=0;printf("请输入一组数字以-1为结束！！\n");p=r=(linklist)malloc(sizeof(londe));scanf("%d",&p->data);while(p->data!=-1){n=n+1;if(n==1)L=p;elser->next=p;r=p;p=(linklist)malloc(sizeof(londe));scanf("%d",&p->data);}r->next=NULL;}void deleted(linklist &L) //删除链表中某个数据{linklist p,cur;int mm;p=L;cur=p->next;printf("请输入要删除的数：");scanf("%d",&mm);while(cur!=NULL&&cur->data!=mm){p=cur;cur=cur->next;}if(cur==NULL)printf("找不到节点");else{p->next=cur->next;free(cur);}}void insert(linklist &L) //插入数据（头插法）{linklist p;int nn;printf("请输入要插入的数据\n");scanf("%d",&nn);p=(linklist)malloc(sizeof(londe));p->data=nn;p->next=L;L=p;}void length(linklist &L){int sum=0;linklist p=L;while(p!=NULL){sum++;p=p->next;}printf("一共有%d个数字\n",sum);}void daoxuprint(linklist &L) //倒叙输出{linklist p=L;int a[100],sum=0;printf("收到圣诞节%d\n",p->data);while(p!=NULL){a[sum]=p->data;p=p->next;sum++;}for(int i=sum-1;i>=0;i--)printf("%d ",a[i]);}void search(linklist &L) //搜索某个数的位置{linklist p=L;int serch;printf("输入你要搜索的的数字");scanf("%d",&serch);if(p!=NULL&&p->data==serch)printf("你要找的数字在表头\n");elseprintf("无接点\n");while(p->next!=NULL){if(p->next->data==serch){printf("要找的数字的前驱为;%d\n",p->data);break;}p=p->next;}}void serprate(linklist &L ) //分开奇数和偶数{linklist p=L,t,head1,head2;linklist pa,pb;head1=create();head2=create();pa=head1;pb=head2;p=L;while(p!=NULL){t=create();if(p->data%2==0){t->data=p->data;pa->next=t;pa=pa->next;}else{t->data=p->data;pb->next=t;pb=pb->next;}p=p->next;}pa->next=NULL;pb->next=NULL;printf("分开奇数和偶数之后为：\n");printf("偶数链表为：\n");print(head1->next);printf("奇数链表为：\n");print(head2->next);}void deletesame(linklist &L) //删除相同的数据{linklist p,q;p=L;q=L->next;while(q){if(p->data==q->data){p->next=q->next;free(q);q=p->next;}else{p=q;q=q->next;}}print(L);}void print(linklist &L) //打印出链表{linklist p;p=L;if(p!=NULL)do{printf("%d ",p->data);p=p->next;}while(p->next!=NULL);printf("%d",p->data);printf("\n");}int main(){linklist L;int dd;printf("请输入菜单：\n");printf("1:输入一组数据创建链表，以-1为结束！！\n");printf("2:删除一个数！\n");printf("3:插入一个数据\n");printf("4:计算链表的长度\n");printf("5:倒叙输出链表\n");printf("6:奇数和偶数分开操作\n");printf("7:删除相同的数据\n");while(scanf("%d",&dd),dd){switch(dd){case 1: createlist(L);print(L);break;case 2: deleted(L);print(L);printf("删除成功！！\n");break;case 3: insert(L);print(L);printf("插入成功！！\n");break;case 4:length(L);print(L);break;case 5: daoxuprint(L);break;case 6:serprate(L);break;case 7:deletesame(L);break;}printf("请输入菜单：\n");printf("1:输入一组数据创建链表，以-1为结束！！\n");printf("2:删除一个数！\n");printf("3:插入一个数据\n");printf("4:计算链表的长度\n");printf("5:倒叙输出链表\n");printf("6:奇数和偶数分开操作\n");printf("7:删除相同的数据\n");}return 0;}作者：郑州轻工业学院计算机科学与技术10-01 QQ389878212。

合集下载

数据结构实验报告--单链表

数据结构实验报告--单链表

数据结构实验报告--单链表数据结构实验报告--单链表1.引言1.1 研究目的本实验旨在通过实践的方式，深入了解单链表的数据结构以及相关操作，提升对数据结构的理解和应用能力。

1.2 实验内容本实验主要包括以下几个方面的内容：●单链表的基本定义和实现●单链表的插入、删除、遍历操作●单链表的逆置操作●单链表的查找和修改操作2.理论基础2.1 单链表的定义单链表是一种常见的线性数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。

2.2 单链表的基本操作①单链表的插入操作在单链表中，可以通过插入操作在指定位置插入一个新节点，该操作主要包括以下步骤：●创建一个新的节点，并为其赋值●将新节点的next指针指向插入位置的后一个节点●将插入位置的前一个节点的next指针指向新节点②单链表的删除操作在单链表中，可以通过删除操作删除指定位置的节点，该操作主要包括以下步骤：●将删除位置的前一个节点的next指针指向删除位置的后一个节点●释放删除节点的内存③单链表的遍历操作单链表的遍历操作主要是依次访问链表中的每一个节点，并执行相应的操作。

④单链表的逆置操作单链表的逆置操作可以将一个单链表中的节点顺序进行颠倒。

⑤单链表的查找操作在单链表中，可以通过查找操作找到指定值的节点。

⑥单链表的修改操作在单链表中，可以通过修改操作修改指定位置的节点的值。

3.实验过程3.1 实验环境本次实验使用C语言进行编程，需要先安装相应的编程环境，如gcc编译器。

3.2 实验步骤①单链表的创建和初始化首先创建一个空链表，并初始化链表的头指针。

②单链表的插入操作按照需求，在链表的指定位置插入一个新节点。

③单链表的删除操作按照需求，删除链表中的指定位置的节点。

④单链表的遍历操作依次访问链表中的每一个节点，并输出其值。

⑤单链表的逆置操作将单链表中的节点顺序进行逆置。

⑥单链表的查找操作按照需求，在链表中查找指定值的节点。

3.2.7 单链表的修改操作按照需求，修改链表中指定位置的节点的值。

数据结构-单链表基本操作实现（含全部代码）

数据结构-单链表基本操作实现（含全部代码）

数据结构-单链表基本操作实现（含全部代码）今天是单链表的实现，主要实现函数如下：InitList(LinkList &L) 参数：单链表L 功能：初始化时间复杂度 O(1)ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度时间复杂度O(n)ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插时间复杂度O(n)[加⼊了查找]若已知指针p指向的后插 O(1)ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素时间复杂度O(n)[加⼊了查找]若已知p指针指向的删除最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。

最坏是O(n),即从头查找p之前的结点,然后删除p所指结点LocateElem(LinkList L,ElemType e) 参数：单链表L，元素e 功能：查找第⼀个等于e的元素，返回指针时间复杂度O(n)代码：/*Project: single linkeed list (数据结构单链表)Date: 2018/09/14Author: Frank YuInitList(LinkList &L) 参数：单链表L 功能：初始化时间复杂度 O(1)ListLength(LinkList L) 参数：单链表L 功能：获得单链表长度时间复杂度O(n)ListInsert(LinkList &L,int i,ElemType e) 参数：单链表L,位置i，元素e 功能：位置i后插时间复杂度O(n)[加⼊了查找]若已知指针p指向的后插 O(1)ListDelete(LinkList &L,int i) 参数：单链表L，位置i 功能：删除位置i元素时间复杂度O(n)[加⼊了查找]若已知p指针指向的删除最好是O(1),因为可以与后继结点交换数据域，然后删除后继结点。

PTA7-4单链表基本操作

PTA7-4单链表基本操作

PTA7-4单链表基本操作7-4 单链表基本操作请编写程序实现单链表插⼊、删除结点等基本算法。

给定⼀个单链表和⼀系列插⼊、删除结点的操作序列，输出实施上述操作后的链表。

单链表数据域值为整数。

输⼊格式:输⼊第1⾏为1个正整数n，表⽰当前单链表长度；第2⾏为n个空格间隔的整数，为该链表n个元素的数据域值。

第3⾏为1个正整数m，表⽰对该链表施加的操作数量；接下来m⾏，每⾏表⽰⼀个操作，为2个或3个整数，格式为0 k d或1 k。

0 k d表⽰在链表第k个结点后插⼊⼀个数据域值为d的结点，若k=0则表⽰表头插⼊。

1 k表⽰删除链表中第k个结点，此时k不能为0。

注：操作序列中若含有不合法的操作（如在长度为5的链表中删除第8个结点、删除第0个结点等），则忽略该操作。

n和m不超过100000。

输出格式:输出为⼀⾏整数，表⽰实施上述m个操作后的链表，每个整数后⼀个空格。

输⼊数据保证结果链表不空。

输⼊样例:51 2 3 4 550 2 80 9 60 0 71 01 6输出样例:7 1 2 8 3 5参照课本的实现#include<iostream>#include<iomanip>#include<stdlib.h>using namespace std;typedef int ElemType;typedef int Status;#define ERROR 0#define OK 1#define OVERFLOW 3typedef struct LNode{ElemType data;struct LNode *next;}LNode ,*LinkList;Status ListInsert(LinkList L,int i,ElemType e){int j=0;LinkList p=L,s;while(p&&j<i-1) // 寻找第i-1个结点{p=p->next;j++;}if(!p||j>i-1) // i⼩于1或者⼤于表长return ERROR;s=(LinkList)malloc(sizeof(LNode)); // ⽣成新结点s->data=e; // 插⼊L中s->next=p->next;p->next=s;return OK;}Status ListDelete(LinkList L,int i){int j=0;LinkList p=L,q;while(p->next&&j<i-1) // 寻找第i个结点,并令p指向其前趋{p=p->next;j++;}if(!p->next||j>i-1) // 删除位置不合理return ERROR;q=p->next; // 删除并释放结点p->next=q->next;free(q);return OK;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);LinkList L;L=(LinkList)malloc(sizeof(LNode)); // 产⽣头结点,并使L指向此头结点 if(!L) // 存储分配失败exit(OVERFLOW);L->next=NULL;int n=0,m=0;LinkList db=L,da;cin>>n;for(int i=0;i<n;i++){da=(LinkList)malloc(sizeof(LNode));cin>>da->data;da->next=NULL;db->next=da;db = da;}cin>>m;for(int i=0;i<m;i++){int o,x,y;cin>>o;if(o==0){cin>>x>>y;ListInsert(L,x+1,y);}else if(o==1){cin>>x;ListDelete(L,x);}else{exit(ERROR);}}LinkList p=L->next;while(p!=NULL){cout<<p->data<<" ";p = p->next;}return 0;}。

单链表基本操作的实现

单链表基本操作的实现

单链表基本操作的实现单链表是一种常见的数据结构，它由多个节点组合而成，每个节点包含一个数据元素和一个指向下一个节点的指针。

通过指针，我们可以方便地在单链表中进行插入、删除和遍历等操作。

以下是关于单链表基本操作的实现。

1. 单链表的创建单链表的创建需要定义一个空的头结点，它的作用是方便在链表的头部进行添加和删除节点操作。

一个空的头节点可以在链表初始化的过程中进行创建。

```typedef struct Node{int data;struct Node *next;}Node;Node *createList(){Node *head = (Node*)malloc(sizeof(Node)); //创建空的头节点head->next = NULL;return head; //返回头节点的地址}```2. 单链表的插入单链表的插入可以分为在链表头部插入、在链表尾部插入和在链表中间插入三种情况。

a. 在链表头部插入节点：```void insertAtHead(Node *head, int data){Node *node = (Node*)malloc(sizeof(Node));node->data = data;node->next = head->next;head->next = node;}```b. 在链表尾部插入节点：```void insertAtTail(Node *head, int data){Node *node = (Node*)malloc(sizeof(Node));node->data = data;node->next = NULL;Node *p = head;while(p->next != NULL){p = p->next;}p->next = node;}```c. 在链表中间插入节点：```void insertAtMid(Node *head, int data, int pos){ Node *node = (Node*)malloc(sizeof(Node)); node->data = data;node->next = NULL;Node *p = head;int count = 0;while(p->next != NULL && count < pos-1){ p = p->next;count++;}if(count == pos-1){node->next = p->next;p->next = node;}else{printf("插入位置错误!");}}```3. 单链表的删除单链表的删除可以分为在链表头部删除、在链表尾部删除和在链表中间删除三种情况。