This article is mainly about my organization of the data structure. If you get any problems，you can ask me on GitHub.
1 存储方式
1.1 顺序表示
#include<stdio.h>
#include<stdlib.h>
#define addsize 10
#define initsize 100
#define ok 1
#define OVERFLOW 0
#define ERROR 0
typedef int elemtype;
typedef int status;
typedef struct list
{
elemtype *elem;
int length;
int size;
}sqlist;
status InitList(sqlist *l)
{
l->elem=(elemtype *)malloc(initsize*sizeof(elemtype));
if(!(l->elem)) exit(OVERFLOW) ;
l->length=0;
l->size=initsize;
return 0;
}
status ListInsert(sqlist *l,int i,elemtype e)
{
elemtype *newelem,*p,*q;
if((i>l->length+1)||(i<1)) return ERROR;
if((l->length)>=(l->size))
{
newelem=(elemtype *)realloc(l->elem,(l->size+addsize)*sizeof(elemtype));
if(!newelem) exit(OVERFLOW);
l->elem=newelem;
l->size+=addsize;
}
q=&(l->elem[i-1]);
p=&(l->elem[l->length]);
for(p;p>q;p--)
*p=*(p-1);
*p=e;
l->length+=1;
return 0;
}
status fun1(elemtype p,elemtype e)
{
if(p%10==e) return 1;
else return 0;
}
status LocateElem(sqlist l,elemtype e,status (*fun1)(elemtype,elemtype))
{
int i=1;
elemtype *p=(l.elem);
while((i<=l.length)&&!(*fun1)(*p++,e)) ++i;
if(i<=l.length) return i;
else return 0;
}
status ListDelete(sqlist *l,int i,elemtype *e)
{
elemtype *p,*q;
if(i<1||i>l->length) return ERROR;
if((!(l->length))||((l->elem[i-1]%2)!=0)) return 0;
p=&(l->elem[l->length-1]);
q=&(l->elem[i-1]);
*e=*q;
for(++q;q<=p;q++)
*(q-1)=*q;
l->length--;
return ok;
}
status fun2(elemtype m)
{
printf("%d ",m);
return ok;
}
status ListTraverse(sqlist l, status (*fun2) (elemtype m))
{
if(!(l.length)) return ERROR;
elemtype *p=l.elem;
int i=1;
printf("遍历检验：") ;
while(i<=l.length&&(*fun2)(*p++)) i++;
printf("\n\n") ;
return ok;
}
int main()
{
sqlist l;
int i,e,location,m,j=30;
InitList(&l);//操作A
ListTraverse(l, fun2);
printf("B测试: \n"); //操作B
for(i=1;i<=30;i++)
{
e=rand()%100+1;
ListInsert(&l,i,e);
}
ListTraverse(l, fun2);
printf("C测试: \n"); //操作C
location=LocateElem(l,5,fun1);
printf("第一个个位5的位置：%d\n",location);
ListTraverse(l, fun2);
printf("D测试: \n"); //操作D
printf("删除的偶数：");
for(i=1;i<=j;i++)
{
e=0;
m=ListDelete(&l, i, &e);
if(m)
{
i--;j--;
printf("%d ",e);
}
}
printf("\n");
ListTraverse(l, fun2);
return 0;
} 1.2 链式表示
1.2.1 单链表
练习1 逆序插入
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}Node,*linklist;
linklist create()
{
printf("请输入测试数据：");
linklist h,r,s;
int x;
h=(linklist)malloc(sizeof(Node));
r=h;
r->next=0;
scanf("%d",&x);
while(x!=-1)
{
s=(linklist)malloc(sizeof(Node));
s->data=x;
s->next=r->next;
r->next=s;
scanf("%d",&x);
}
return h;
}
void funa(linklist head)
{
printf("A:请输出链表结点值：");
linklist p;
p=head->next;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
void funb(linklist head)
{
printf("B:请输出链表结点值：");
linklist p,q,s;
p=head->next;
q=head;
while(p)
{
if((p->data)%2==0)
{
s=(linklist)malloc(sizeof(Node));
s->data=3*(p->data);
s->next=q->next;
q->next=s;
printf("%d ",s->data);
}
q=p;
p=p->next;
printf("%d ",q->data);
}
printf("\n");
}
void func(linklist head)
{
printf("C:请输出链表结点值：");
linklist p,q,s;
p=head->next;
q=head;
while(p)
{
if((p->data)%10==2)
{
s=p;
p=p->next;
q->next=p;
free(s);
}
else
{
q=p;
p=p->next;
}
}
p=head->next;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
}
int main()
{
linklist head;
head=create();
funa(head);
funb(head);
func(head);
return 0;
}
/*1 2 3 4 5 -1*/ 练习2 求最值
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}Node,*Linklist;
Linklist create()//创建链表
{
Linklist h,r,s;
h=(Linklist)malloc(sizeof(Node));
r=h;
for(int m=1;m!=-1;m=s->data)//以-1作结束标志
{
s=(Linklist)malloc(sizeof(Node));
scanf("%d",&s->data);
r->next=s;
r=s;
}
r->next=0;
return h;
}
void find(Linklist listhead,int *big,int *small)//求最值并输出
{
Linklist p;
p=listhead->next;
*big=p->data;
*small=p->data;
for(;p->next!=0;)
{
if(p->data>*big) *big=p->data;
if(p->data<*small) *small=p->data;
p=p->next;
}
}
int main()//主函数
{
int max,min;
printf("请输入测试数据：");
Linklist head;
head=create();
find(head,&max,&min);
printf("请输出最值：min=%d max=%d\n",min,max) ;
return 0;
}
/*测试样例 4 25 90 34 17 86 63 48 51 15 -1*/1.2.2 静态链表
#include<stdio.h>
#define maxsize 100
typedef char elemtype;
typedef struct{
elemtype data;
int cur;
}component,sqlinklist[maxsize];
void init_list(sqlinklist space)
{
for(int i=0;i<maxsize-1;i++)
{
space[i].cur=i+1;
}
space[maxsize-1].cur=0;
}
int malloc_list(sqlinklist space)
{
int i=space[0].cur;
if(i!=0)
space[0].cur=space[i].cur;
return i;
}
void free_list(sqlinklist space,int a)
{
space[a].cur=space[0].cur;
space[0].cur=a;
}
int create_list(sqlinklist space,int m)
{
int s,r,i;
s=malloc_list(space);
r=s;
for(int j=0;j<m;j++)
{
i=malloc_list(space);
scanf("%c",&space[i].data);
space[r].cur=i;
r=i;
}
space[r].cur=0;
return s;
}
void insert_list(sqlinklist space,int r,elemtype b)
{
int i=malloc_list(space);
space[i].data=b;
space[i].cur=space[r].cur;
space[r].cur=i;
}
void delete_list(sqlinklist space,int s,elemtype c)
{
int p,q;
q=s;
while(q)
{
p=q;
q=space[q].cur;
if(space[q].data==c) break;
}
space[p].cur=space[q].cur;
free_list(space,q);
}
int locate_list(sqlinklist space,int s,elemtype c)
{
int q;
q=s;
while(q)
{
q=space[q].cur;
if(space[q].data==c) break;
}
if(q) return 1;
else return 0;
}
void traverse_list(sqlinklist space,int s)
{
int q=space[s].cur;
while(q)
{
printf("%c",space[q].data);
q=space[q].cur;
}
}
int main()
{
sqlinklist space;
init_list(space);
int m,n,s;
char c;
scanf("%d%d",&m,&n);
getchar();
s=create_list(space,m);
getchar();
int r=s;
while(r)
{
r=space[r].cur;
if(space[r].cur==0) break;
}
for(int j=0;j<n;j++)
{
scanf("%c",&c);
if(locate_list(space,s,c)) delete_list(space,s,c);
else insert_list(space,r,c);
}
traverse_list(space,s);
return 0;
} 1.2.3 循环链表
将链表的最后一个结点与第一个结点连接起来，可从任意结点出发访问其它结点
1.2.4 双向链表
每个结点中有两个指针，一个指向其后继结点，另一个指向其前趋结点
2 习题
1.假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，设计算法，求一个新的集合A＝A∪B
==*加代码==
2.已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。
==*加代码==
3 附录——ADT定义
ADT List {
数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n, n≥0 }
数据关系：R1＝{<ai-1 ,ai>|ai-1 ,ai∈D, i=2,...,n }
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L。
ListLength(L)
初始条件：线性表L已存在。
操作结果：返回L中元素个数。
GetElem(L, i, &e)
初始条件：线性表L已存在， 1≤i≤ListLength(L)
操作结果：用e返回L中第i个元素的值
LocateElem(L, e, compare( ))
初始条件：线性表L已存在.
操作结果：返回L中第1个与e满足关系compare( )的元素的位序，不存在则返回0。重要：ADT中compare()这种形式，语言级别对应为函数指针！
ListInsert(&L, i, e)
初始条件：L已存在，1≤i≤ListLength(L)+1
操作结果：在L的第i个位置插入新的元素e，L的长度增1
ListDelete(&L, i, &e)
初始条件：L已存在且非空，1≤i≤ListLength(L)
操作结果：删除L的第i个元素，并用e返回其值，L的长度减1
ListTraverse(L, visit( ))
初始条件：线性表L已存在
操作结果：依次对L的每个数据元素调用visit()函数，若visit()失败则操作失败
}ADT List
