单链表和循环链表

单链表：

（构建一个结构体，里面包含data用于储存每个节点的数据，还要包含一个用于指向下一个结点的指针*next）

typedef struct node//typedef 用于起别名

{

int data;

struct node *next;

}Node;//Node是typedef给结构体起的别名，用于让编译器识别，Node是结构体类型

建立一个单链表所需的一系列操作函数：

1.初始化头结点：head->next=NULL;

2.头插法，将后面的每个数据从头结点后面插入

3.尾接法，将待插入的数据往末尾插入这两种方法都是用来插入数据，顺序不一样

4.开辟内存空间：具体怎么实现以上插入数据操作，这就要靠开辟内存空间来实现了，每插入一个数据，都要开辟一个内存空间(结点)来存放数据，再将它用头插法或尾接法插入链表

5.删除操作函数：参数部分得包括头结点(用于找到target)和target

.......

代码如下:

#include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node *next; }Node; //头插法 Node *insert(Node *head,int e) { Node *L=(Node *)malloc(sizeof(Node)); L->data=e; if(head->next==NULL) { head->next=L; L->next=NULL; } else{ L->next=head->next; head->next=L; } return head; } //去尾巴 Node *deletnode(Node *head) { Node *tail=head; if(tail->next==NULL) return head; while(tail->next!=NULL) { tail=tail->next; } Node *p=head; while(p->next!=tail) { p=p->next; } free(tail); p->next=NULL; return head; } //遍历匹配 int compare(Node *head,int e) { Node *p=head->next; while(p!=NULL) { if(p->data==e) { return 1;//有相同的 break; } p=p->next; } return -1;//没有相同的 } //计数 int count(Node *head) { int sum=0; Node *p=head; while(p->next!=NULL) { sum++; p=p->next; } return sum; } int main() { int M,N; scanf("%d %d",&M,&N); int i=0,j=0; int arr[N]; for(i=0;i<N;i++) scanf("%d",&arr[i]); Node *head=(Node *)malloc(sizeof(Node)); head->next=NULL; head->data=0; int k=-1,sum=0; while(N--) { k++; int len=count(head); if(compare(head,arr[k])==1) continue; else { if(len>=M) head=deletnode(head); sum++; } head=insert(head,arr[k]); } printf("%d\n",sum); return 0; }

循环链表：

在单链表的基础上将尾结点连接至头结点上去

函数操作和单链表的一系列操作一样

代码如下：

#include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node*next; }Node; //头插法，用来初始化，将数据放进去 Node *insert(Node *head,int e) { Node *L=(Node *)malloc(sizeof(Node)); L->data=e; if(head->next==head) { head->next=L; L->next=head; } else { L->next=head->next; head->next=L; } return head; } //删除数据 Node *deletnode(Node *head,Node *pre,Node *target) { pre->next=target->next; free(target); return head; } //打印函数 void print(Node *head) { if(head->next==head) { printf("链表为空\n"); return; } else { Node *p=head->next; while(p->next!=head) { printf("%d ",p->data); p=p->next; } printf("%d",p->data); } } int main() { //给链表初始化 Node *head=(Node *)malloc(sizeof(Node)); if(head==NULL) { printf("内存分配失败\n"); return 1; } head->next=head; head->data=0; //将1-10给放进去 for(int i=10;i>=1;i--) { head=insert(head,i); } int N; scanf("%d",&N); while(N--) { int m; scanf("%d",&m); Node *target=head; while(target->next!=head) { if(target->data==m) break; target=target->next; } Node *pre=head; while(pre->next!=head) { if(pre->next->data==m) break; pre=pre->next; } head=deletnode(head,pre,target); //将删除的元素放入最前端 head=insert(head,m); print(head); printf("\n"); } return 0; }