【算法设计-链表】单链表与双向循环链表

1.单链表代码：包含了尾插法，插入，删除操作。

有头结点的单链表也是为了在第一个位置插入和删除时候容易，不需要另外讨论

#include<stdio.h>
#include<stdlib.h>
typedef struct Linklist
{
 int key;
 Linklist *next;
}Linklist;
Linklist* create_end()
{
  Linklist *head=(Linklist *)malloc(sizeof(Linklist));
  Linklist *e,*p;
  e=head;
  printf("输入值?以#结束\n");
  int ch;
  while((scanf("%d",&ch))==1)
  {
 p=(Linklist *)malloc(sizeof(Linklist));
 p->key=ch;
 e->next=p;
 e=p;
  }
  e->next=NULL;
  printf("done\n");
  return head;//这里返回头结点而不是head->next,目的就是为了后面的插入和删除时候可以在第一个位置插入和删除
}
void add(Linklist* head)
{
Linklist *q=head;
Linklist *p=(Linklist*)malloc(sizeof(Linklist));
int ch;
printf("要插入的位置:");
fflush(stdin);
scanf("%d",&ch);
int i=1;//i要从1开始
while(i!=ch)
{
q=q->next;
i++;
}
p->next=q->next;
q->next=p;
    printf("要插入的数据是多少:");
fflush(stdin);
scanf("%d",&ch);
p->key=ch;
}
void delete_s(Linklist* head)
{
printf("要删除第几个位置:");
int ch;
fflush(stdin);
scanf("%d",&ch);
Linklist *p=head;
Linklist *q=p->next;
int i=1;
while(i!=ch)
{
q=q->next;
p=p->next;
i++;
}
p->next=q->next;
printf("删除了%d",q->key);
delete q;
}
void show_Linklist(Linklist* head)
{
Linklist* p=head->next;//为了不输出头结点的值要从head->next开始
while(p->next!=NULL)
{
printf("%d->",p->key);
p=p->next;
}
printf("%d",p->key);
}
int main(void)
{
Linklist *head=new Linklist;
head=create_end();
add(head);
show_Linklist(head);
delete_s(head);
show_Linklist(head);
return 0;
}

结果展示：

2.双向循环链表：包含尾插，插入，删除

本文中循环链表包含头结点。这样做的好处是为了在第一个位置插入和删除都很容易

插入操作：

注意：要始终以头结点后面一个节点作为标杆指针计算

代码：

#include<stdio.h>
#include<stdlib.h>
typedef struct Linklist
{
 int key;
 Linklist *prior;
 Linklist *next;
}Linklist;
Linklist* create_end()
{
  Linklist *head=(Linklist *)malloc(sizeof(Linklist));
  head->key=0;
  Linklist *e,*p;
  e=head;
  printf("输入值?以#结束\n");
  int ch;
  while((scanf("%d",&ch))==1)
  {
 p=(Linklist *)malloc(sizeof(Linklist));
 p->key=ch;
 e->next=p;
 p->prior=e;
 e=p;
  }
  e->next=head;
  head->prior=e;
  printf("done\n");
  return head;
}
void add(Linklist* head)
{
Linklist *p=head->next;
Linklist *r=(Linklist*)malloc(sizeof(Linklist));
int ch;
printf("要插入的位置:");
fflush(stdin);
scanf("%d",&ch);
int i=1;
while(i!=ch)
{
p=p->next;
i++;
}
printf("要插入的数据是多少:");
scanf("%d",&ch);
r->key=ch;
r->next=p;//注意这里的写法
r->prior=p->prior;
r->prior->next=r;
p->prior=r;
   
}
void delete_s(Linklist* head)
{
Linklist *p=head->next;//这里要有next
if(p->next==head)
{
printf("不能删除了，已经空了!\n");
}
printf("要删除第几个位置:");
int ch;
fflush(stdin);
scanf("%d",&ch);
int i=1;
while(i!=ch)
{
p=p->next;
i++;
}
p->prior->next=p->next;

p->next->prior=p->prior;

printf("删除了%d\n",p->key);
delete p;
}
void show_Linklist(Linklist* head)
{
Linklist *p=head->next;
while(p->next!=head)
{
printf("%d->",p->key);
p=p->next;
}
printf("%d",p->key);
}
int main(void)
{
Linklist *head=new Linklist;
head=create_end();
add(head);
show_Linklist(head);
delete_s(head);
show_Linklist(head);
return 0;
}