线性表（持续更新中）

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