线性表完整代码-白红宇

线性表完整代码

阅读量：5014 次

发布时间：2019-06-12

本文共 11577 字，大约阅读时间需要 38 分钟。

顺序存储：

#include
     
      #include
      
       typedef int Position;typedef int ElementType;typedef struct LNode *PtrToLNode;#define MAXSIZE 10struct LNode{    ElementType Data[MAXSIZE];    Position Last;};typedef PtrToLNode List;List MakeEmpty(){    List P;    P = (List)malloc(sizeof(struct LNode));    P->Last = -1;    return P;}bool Insert(List L,Position n,ElementType x){    if(L->Last == MAXSIZE - 1)    {        printf("表满");        return false;    }    if(n<1 || n>L->Last+1+1){        printf("位序不合法");        return false;    }    for(int j = L->Last;j>=n-1;j--)    {        L->Data[j+1] = L->Data[j];    }    L->Data[n-1] = x;    L->Last++;    return true;}Position Find(List L,ElementType x){    int j;    for( j = 0;j
       
        Last+1;j++)    {        if(x == L->Data[j])        {                printf("查找的下表%d位序为：%d\n",L->Data[j],j+1);            return 0;        }    }    if(j >= L->Last)    {        printf("查找的不存在");    }    return 0;        }bool Delete(List L,Position n){        if(L->Last == MAXSIZE - 1)    {        printf("表满");        return false;    }    if(n<1 || n>L->Last+1){        printf("位序不合法");        return false;    }    for(int j = n-1;j
        
         Last+1;j++)    {        L->Data[j] = L->Data[j+1];    }    L->Last--;    return true;}int Length(List L){    return L->Last+1;} int Printf(List L){    for(int i = 0 ; i
         
          Last+1;i++)        printf("%d  ",L->Data[i]);    printf("\n");    return 0;}int main(){    List L;    L = MakeEmpty();    Insert(L,1,1);    Insert(L,2,2);    Insert(L,3,3);    Insert(L,4,4);    Printf(L);    printf("表长：%d\n",Length(L));    Find(L,4);    printf("删除一个\n");    Delete(L,2);    Printf(L);    Find(L,4);    printf("表长：%d\n",Length(L));    Insert(L,2,2);    Insert(L,3,33);    Printf(L);    Find(L,33);    Find(L,4);;    return 0;}

线性表的链式存储：

#include
     
      #include
      
       typedef int ElementType;typedef struct LNode * PtrToLNode;struct LNode{    ElementType Data;    PtrToLNode Next;};typedef PtrToLNode Position;//这里的位置是结点的地址 typedef PtrToLNode List; //初始化List MakeEmpty(){    List L;    L = (List)malloc(sizeof (struct LNode));    if (!L)        exit (-1);    L->Next = NULL;    return L;}  //根据指定的位序查找int FindKth(List L,int K){    Position p;    int cnt = 1;//位序从1开始     p = L->Next;     while(p&&cnt
       
         Next;        cnt++;    }    if((cnt==K)&&p) printf("您查找的数为：%d\n",p -> Data);    else printf("您查找数不存在");} //按值查找 Position Find(List L,int X){    Position p;    p = L->Next;     while(p&&p->Data!=X){        p = p-> Next;    }    if(p) printf("查找成功，您查找的数为：%d\n",p->Data);    else printf("您查找数不存在");} //插入List Insert(List L ,ElementType X,int i){    Position tmp,pre;    int cnt =0 ;    pre = L;    while(pre&&cnt
        
         Next;        cnt++;    }    if(pre==NULL||cnt!=i-1){        printf("插入位置参数错误\n");    }    else{        tmp = (Position)malloc(sizeof(struct LNode));        tmp->Data=X;        tmp->Next=pre->Next;        pre->Next=tmp;    }    }  //删除bool Delete(List L,int i){    Position tmp,pre;    int cnt = 0;    pre = L;    while(pre&&cnt
         
          Next;        cnt++;    }    if(pre==NULL||cnt!=i-1||pre->Next==NULL){        printf("删除位置参数错误");    }    else{        tmp = pre->Next;        pre->Next = tmp->Next;        free(tmp);        printf("删除成功");     }}  //求表长int Length(List L){    Position p;    int cnt = 0;    p = L->Next;    while(p){        p = p -> Next;        cnt++;    }    return cnt;}  void DisLinkList(List L){    List p = L->Next;    printf("输出链表： ");     while (p)    {        printf("%d ", p->Data);        p = p->Next;    }} int main(){    Position pre;    Position L = MakeEmpty();    pre = L;    int i,n,x,len,cz,del;    //插入     scanf("%d",&n);    for(i=1;i<=n;i++){        scanf("%d",&x);        Insert(pre,x,i);    }    //输出     DisLinkList(pre);    printf("\n");    //求表长     len = Length(L);    printf("表长为：%d",len);    printf("\n");    //按值查找    printf("请输入你要按值查找的数：\n");    scanf("%d",&cz);    Find(L,cz);    printf("\n");    //按序号查找    printf("请输入你要按序号查找的数的序号：\n");    scanf("%d",&cz);    FindKth(L,cz);    printf("\n");    //删除    printf("请输入你要删除的数的下标：\n",del);    scanf("%d",&del);    Delete(L,del);    DisLinkList(pre);    printf("\n");    return 0;}

线性表链式存储二：

#include
     
      #include
      
       typedef int ElementType;typedef struct LNode *PtrToLNode;struct LNode{    ElementType Data;    PtrToLNode next;};typedef PtrToLNode List;typedef List Position;List MakeEmpty(){    PtrToLNode L;    L = (List)malloc(sizeof(struct LNode));    if(!L)        exit(-1);    L->next = NULL;    return L;};bool Insert(List L,int i,ElementType x ){    Position tmp,pre;    int cnt = 0;    pre = L;    while(pre && cnt < i - 1){        pre = pre->next;        cnt++;    }        if(pre == NULL || cnt!=i-1){        printf("插入位置不合法\n");        return false;        }    else{        tmp = (List)malloc(sizeof(struct LNode));        tmp->Data = x;        tmp->next = pre->next;        pre->next = tmp;        printf("插入完成\n");    }    return true;}void Find(List L,ElementType x){    Position pre;    int cnt = 0;    pre = L->next;    while(pre!=NULL && pre->Data != x)    {        pre = pre->next;        cnt++;    }    if(pre)    {        printf("%d的位序为%d\n",pre->Data,cnt);    }    else{        printf("%d没有找到\n",x);    }}void FindKth(List L,int k){    Position pre;    pre = L->next;    int cnt = 0;    while(pre && cnt 
       
        next;        cnt++;    }    if(k-1 == cnt)        printf("在%d位置的为%d\n",k,pre->Data);    else        printf("位序不合法\n");}bool Delete(List L,ElementType x){    Position pre,tmp,tmp1;    pre = L->next;    while(pre && pre->Data != x){        tmp = pre;        pre = pre->next;            }    if(pre){        tmp1 = pre;        tmp->next = tmp1->next;        free(tmp1);        printf("删除%d成功\n",x);            return true;    }    else{        printf("没有找到%d\n",x);        return false;    }}bool DeleteKth(List L,int l){    Position pre,tmp;    int cnt = 0;    pre = L;    while(pre && cnt < l - 1 ){        pre = pre->next;        cnt++;    }    if(pre ==NULL || cnt != l - 1 || pre->next == NULL){        printf("删除位置错误\n");        return false;    }else{        tmp = pre ->next;        pre ->next = pre->next->next;                printf("在位置%d删除%d成功\n",l,tmp->Data);        free(tmp);        return true;    }}void Length(List L){    Position p;    int cnt = 0;    p = L->next;    while(p){        p = p -> next;        cnt++;    }    printf("长度为：%d\n",cnt); } void Print(List L){    Position pre;    pre = L->next;    while(pre){        printf("%d ",pre->Data);        pre =pre->next;    }    printf("\n");}int main(){    PtrToLNode L;    L = MakeEmpty();    Insert(L,22,22);    Insert(L,1,1);    Insert(L,2,2);    Print(L);    Find(L,2);    FindKth(L,1);    Find(L,33);    Insert(L,3,3);    Insert(L,4,4);    Insert(L,4,41);    Print(L);    Delete(L,4);    DeleteKth(L,3);    Print(L);    Length(L);    return 0;}

多项式的加法运算：

#include
     
      #include
      
       typedef struct PolyNode *Polynomial;struct PolyNode{    int coef;//系数    int expon;//指数     Polynomial link;//链表指针域指向下一地址 };Polynomial ReadPoly();//读入多项式void Attach(int c,int e,Polynomial *pRear);//将每次读入的多项式连接 Polynomial Add(Polynomial P1,Polynomial P2);//多项式相加 Polynomial Mult(Polynomial P1,Polynomial P2);//多项式相乘 int Compare(int a,int b);//比较 void PrintPoly(Polynomial P);//输出多项式 int main(void){    Polynomial P1,P2,PS,PP;        P1=ReadPoly();//读入数据    P2=ReadPoly();        PP=Mult(P1,P2);//多项式相乘     PrintPoly(PP);        printf("\n");        PS=Add(P1,P2);//多项式相加     PrintPoly(PS);        return 0;}Polynomial ReadPoly()//读入数据 {    Polynomial P,Rear,t;    int c,e,N;     scanf("%d",&N);    P=(Polynomial)malloc(sizeof(struct PolyNode));//为方便表头插入，先产生一个临时空节点做为链表头    P->link =NULL;    Rear=P;//Rear始终指向链表的尾部    while(N--)    {                scanf("%d %d",&c,&e);        if(c!=0)//对系数为零的项进行判断         Attach(c,e,&Rear);    }    t=P;//释放表头为空的节点     P=P->link;    free(t);    return P;}void Attach(int c,int e,Polynomial *pRear)//将数据连接成链表 {    Polynomial P;    P=(Polynomial)malloc(sizeof(struct PolyNode));//为方便表头插入，先产生一个临时空节点做为链表头    P->coef=c;    P->expon=e;    P->link =NULL;    (*pRear)->link=P;//将P指向的新节点插入到当前结果表达式尾项的后面    *pRear=P;//最后一项指向P}int Compare(int a,int b)//比较 ，a>b return 1，a
       b)    return 1;    else if(a==b)    return 0;    else    return -1;}Polynomial Add(Polynomial P1,Polynomial P2)//多项式相加 {    Polynomial front,rear,temp;//front为头，Rear为尾    int sum;    rear=(Polynomial)malloc(sizeof(struct PolyNode));//为方便表头插入，先产生一个临时空节点做为链表头    front=rear;    while(P1&&P2)        switch(Compare(P1->expon ,P2->expon))        {            case 1://如果P1->expon>P2->expon                Attach(P1->coef,P1->expon,&rear);                P1=P1->link ;                break;            case -1://如果P1->expon
        
         expon                Attach(P2->coef,P2->expon,&rear);                P2=P2->link ;                break;            case 0://如果P1->expon=P2->expon                sum=P1->coef +P2->coef;                if(sum)//如果指数相等，先判断系数和是否为0                 Attach(sum,P1->expon,&rear);                P1=P1->link;                P2=P2->link ;                break;        }        //将未处理完的多项式中所有节点复制到结果多项式中        while(P1)        {            Attach(P1->coef,P1->expon,&rear);            P1=P1->link;        }        while(P2)        {            Attach(P2->coef,P2->expon,&rear);            P2=P2->link;        }        rear->link=NULL;//释放头为空的节点         temp=front;        front=front->link ;        free(temp);        return front;}void PrintPoly(Polynomial P)//打印 {    int flag=0;    if(!P)    {        printf("0 0");        return ;    }        while(P)    {        if(!flag)            flag=1;        else            printf(" ");        printf("%d %d",P->coef ,P->expon );        P=P->link ;    }}Polynomial Mult(Polynomial P1, Polynomial P2)//多项式相乘 {    Polynomial P, Rear;    Polynomial t1, t2, t;    if (!P1 ||!P2)//判断两个链表是否为空    {        return NULL;    }    t1 = P1;    t2 = P2;    P = (Polynomial)malloc(sizeof(struct PolyNode));    Rear = P;    while (t2)//先让t1的第一项和t2的每一项相乘，构建出一个新链表，用于后来数据的插入    {        Attach(t1->coef*t2->coef, t1->expon + t2->expon, &Rear);        t2 = t2->link;    }    t1 = t1->link;    while (t1)    {        t2 = P2;        Rear = P;//Rear每次都从所构建的链表头开始，以便于寻找插入位置         while (t2)         {            int c = t1->coef*t2->coef;            int e = t1->expon + t2->expon;            while (Rear->link&&Rear->link->expon > e)//Rear每次都从所构建的链表头开始，以便于寻找插入位置             {                Rear = Rear->link;            }            if (Rear->link&&Rear->link->expon == e)//相等就不需要申请一个新的节点，只要把系数相加。            {                if (Rear->link->coef + c)//系数和不为0，                {                    Rear->link->coef += c;                }                else//系数和为0，删除节点                {                    t = Rear->link;                    Rear->link = t->link;                    free(t);                }            }            else//如果指数不相等，申请空间将将此项插入            {                t = (Polynomial)malloc(sizeof(struct PolyNode));                t->link = NULL;                t->coef = c;                t->expon = e;                t->link = Rear->link;                Rear->link = t;                Rear = Rear->link;            }            t2 = t2->link;        }        t1 = t1->link;    }    t2 = P;//释放空节点     P = P->link;    free(t2);    return P;}