|
目录
单链表
循环链表
单链表
头文件：
#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef char datatype;//数据类型存储
typedef struct node//定义链表
{
datatype data;
struct node *next;
}linklist;
linklist *head,*p;//head 为头指针，p为工作指针
//头插法创建链表
linklist*Creat_Head();
//尾插法创建链表
linklist*Creat_Tail();
//尾插法建立不带头结点的单链表
linklist*Creat_None_Tail();
//按序号查找单链表
linklist*Get(linklist*head,int i);
//按照值查找
linklist*Locate(linklist*head, datatype key);
//插入单链表
linklist*Insert(linklist*head, datatype x, int i);
//将值为x的新结点插入到递增有序列表中，使得插入后该链表仍然有序
void Insert(linklist*head, datatype x);
//删除单链表
void Delete(linklist*head, int i);
//单循环链表上 将两个线性表合为一个循环列表
linklist*Connect_Tail(linklist*La, linklist*Lb);
//头指针
linklist*Connect_Head(linklist*La, linklist*Lb);
int main()
{
}
实现：
#include "单链表.h"
//头插法创建链表
linklist*Creat_Head()
{
linklist*head, *p;
char ch;
head = (linklist*)malloc(sizeof(linklist));
head->next = NULL;
while ((ch = getchar()) != '/n')
{
p = (linklist*)malloc(sizeof(linklist));
p->data = ch;
p->next = head->next;
head->next = p;
}
return head;
}
//尾插法创建链表
linklist*Creat_Tail()
{
linklist*head, *p, *r;
char ch;
head = (linklist*)malloc(sizeof(linklist));
head = NULL;
r = head;
while ((ch = getchar()) != '/n')
{
p = (linklist*)malloc(sizeof(linklist));
p->data = ch;
r->next = p;
r = p;
}
r->next = NULL;
return head;
}
//尾插法建立不带头结点的单链表
linklist*Creat_None_Tail()
{
linklist*head, *p,*r;
char ch;
head = (linklist*)malloc(sizeof(linklist));
head = NULL;
r = NULL;
while ((ch = getchar()) != '/n')
{
p = (linklist*)malloc(sizeof(linklist));
p->data = ch;
if (head->next == NULL){
head = p;
}else{
r->next = p;}
r = p;
}
if(r != NULL){
r->next = NULL;
}
return head;
}
//按序号查找单链表
linklist*Get(linklist*head, int i)
{
linklist*p = head;
int j = 0;
while (p->next != NULL && j < i)
{
p = p->next;
j++;
}
if (i == j) { return p; }
else { return NULL; }
}//时间复杂度为O（n）
//按照值查找
linklist*Locate(linklist*head, datatype key)
{
linklist*p = head->next;
while (p!= NULL&& p->data != key)
{
p= p->next ;
}
return p;
}//时间复杂度为O（n）
//插入单链表
linklist*Insert(linklist*head, datatype x, int i)
{
linklist*p, *s;
p = Get(head, i - 1);
if (p == NULL) printf("非法插入位置");
else
{
s = (linklist*)malloc(sizeof(linklist));
s->data = x;
s->next = p->next;
p->next = s;
}
}
//将值为x的新结点插入到递增有序列表中，使得插入后该链表仍然有序
void Insert(linklist*head, datatype x)
{
linklist*s,*q;
s = (linklist*)malloc(sizeof(linklist));
s->data = x;
s->next = NULL;
p = head->next;
q = head;
while (p != NULL&&head->data <= x)
{
q = p;
p = p->next;
}
if (p->next == NULL)q->next = s;
else s->next = p->next; q->next = s;
}//时间复杂度为O（n）
//删除单链表
void Delete(linklist*head, int i)
{
linklist*s;
s = (linklist*)malloc(sizeof(linklist));
p = Get(head, i - 1);
if (p != NULL && p->next != NULL)
{
s = p->next;
p->next = s->next;
free(s);
}
else printf("非法删除位置");
}
//单循环链表上 将两个线性表合为一个循环列表
linklist*Connect_Tail(linklist*La, linklist*Lb)
{//La,Lb是两个非空循环链表的尾指针
linklist*p = La->next;
La->next = Lb->next->next;
free(Lb->next);//先释放内存再合结点
Lb->next = p;
return Lb;
}//时间复杂度为O（1）,返回值为表尾
//头指针
linklist*Connect_Head(linklist*La, linklist*Lb)
{//La,Lb是两个非空循环链表的头指针
linklist*p = La->next;
while (p->next != La)p = p->next;
p->next = Lb->next;
p = Lb->next;
while (p->next != Lb)p = p->next;
p->next = La;
free(Lb);
}//时间复杂度是O（len(LA) + Len(Lb)）
循环链表
头文件：
#pragma once
#include <stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct dnode
{
datatype data;
struct dnode *next,*prior;
}dlinklist;
dlinklist *head;
//双向列表 每次我做的时候都感觉像是蜜雪冰城，你爱我呀我爱你
//在节点*p后插入结点*s 后插法
void DInsertAfter(dlinklist*p, datatype x);
//在节点*pqian插入节点*s 前插法
void DInsertbefore(dlinklist*p, datatype x);
//双向列表的删除
void DDelete(dlinklist*p);
//建立双向列表 头插法
dlinklist*Creat_Head();
//建立双向列表 尾插法
dlinklist*Creat_Tail();
int main()
{
}
实现：
#include "循环链表.h"
//在节点*p后插入结点*s 后插法
void DInsertAfter(dlinklist*p, datatype x)
{//在带头结点的非空双向链表中，将值为x的新节点插入*P之后
dlinklist *s = (dlinklist*)malloc(sizeof(dlinklist));
s->data = x;
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
}//时间复杂度为O（1）
//在节点*pqian插入节点*s 前插法
void DInsertbefore(dlinklist*p, datatype x)
{//在带头结点的非空双向链表中，将值为x的新节点插入*P之前
dlinklist*s = (dlinklist*)malloc(sizeof(dlinklist));
s->data = x;
s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
}//时间复杂度为O（1）
//双向列表的删除
void DDelete(dlinklist*p)
{//在带头结点的非空向双向链表中，删除节点*p，设*p为非终端节点
p->next->prior = p->prior;
p->prior->next = p->next;
free(p);
}//时间复杂度为O（1）
//建立双向列表 头插法
dlinklist*Creat_Head()
{
dlinklist*head, *s;
char ch;
head = (dlinklist*)malloc(sizeof(dlinklist));
head->next = head;
head->prior = head;
printf("Put any char to establish a string:\n");
scanf("%c", ch);
while (ch != '\n')
{
s = (dlinklist*)malloc(sizeof(dlinklist));
s->data = ch;
s->prior = head;
s->next = head->next;
head->next->prior = s;
head->next = s;
scanf("%c", ch);
}
return head;
}
//建立双向列表 尾插法
dlinklist*Creat_Tail()
{
dlinklist*head, *s;
char ch;
head = (dlinklist*)malloc(sizeof(dlinklist));
head->next = head;
head->prior = head;
printf("Put any char to establish a string:\n");
scanf("%c", ch);
while (ch != '\n')
{
s = (dlinklist*)malloc(sizeof(dlinklist));
s->data = ch;
s->prior = head->next;
s->next = head;
head->prior->next = s;
head->prior = s;
scanf("%c", ch);
}
return head;
}
|