設某線性表數據元素的類型為整型，以鏈表結構存儲線性表。試編程實現：

(1) 輸入數據元素，以先進先出形式創建單鏈表

(2) 銷毀單鏈表

(3) 線性表置空

(4) 求線性表長度

(5)在第i個數據元素前插入新的元素

(6) 刪除第i個元素

(7) 顯示線性表中的全部元素

(8) 求最大元素的值和平均值

 

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
#define ERROR     0
#define OK        1
#define OVERFLOW  -2
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

int Create_List(LinkList L,int length)
{//創建一個帶表頭結點的大小為n個的單鏈表
    int i;                   
    LinkList p, tail; //聲明一定要在前面，否則會出錯
        tail=L;
    for(i=0;i<length;i++)
    {
        p=(LinkList)malloc(sizeof(LNode));
        printf("請輸入%d個數據\n",length);
        scanf("%d",&p->data);
        p->next=NULL;
        tail->next=p;
        tail=tail->next;
    }
       return OK;
}

int display_all(LinkList L,int length) //依賴于長度，可是卻不定，長度函數有問題。
{//顯示所有的數據元素
    int i;
    printf("線性表的全部數據元素如下：\n");
    for(i=0;i<length-1;i++)
    {
        printf("%d ",L->next->data);
        L=L->next;
    }
    printf("\n");
    return OK;
}

int length_L(LinkList L) //有問題
{//求得線性表的長度
    int length=0;
    LinkList p=L;
    while(p!=NULL)
    {
        ++length;
        p=p->next;
    }
    return length;
}

int ListInsert(LinkList L,int i ,int *e)
{//插入元素
    LinkList p=L,s;
    int j=0;
    while(p&&j<i-1)
    {
        p=p->next;
        ++j;
    }
     if(!p||j>i-1) return ERROR;
     s=(LinkList)malloc(sizeof(LNode));
     s->data=*e;
     s->next=p->next;
     p->next=s;
     return OK;
}
int ListDelet(LinkList L, int i)
{//刪除指定位置的結點
    LinkList p=L,q;
    int j=0;
    while(p->next&&j<i-1)  //尋找第i-1個結點
    {
        p=p->next;
        ++j;
    }
    if(!(p->next)||j>i-1) return ERROR;
    q=p->next; p->next=q->next;
    free(q);
    return OK;
}
int Destroy_L(LinkList L)   //這里會遇到一個問題，如果將頭結點free掉的話就會出錯，
                            //因為頭結點不是自己分配的，而是系統分配的，在主函數中，所以無法釋放
{
     LinkList head=L,p;
     p=head;
     if (head)
         p = head->next ;
     head = head->next ;
     while(head!=NULL)
     {
         p=head;
         head=head->next;
         free(p);
     }
     return OK;
}
int ClearList(LinkList L)
{//線性表置空
    L->next=NULL;  //將頭結點指針域置為NULL
    return OK;
}
int max_num(LinkList L)
{
    LinkList p=L->next;
    int max=0;
    while(p!=NULL)
    {
        if(max<=p->data)
            max=p->data;
        p=p->next;
    }
    return max;
}

float aver_num(LinkList L)  //注意函數名不要和變量同名，很容易出錯
{ //求出所有元素的平均值
    LinkList p=L->next;
    float average;
    int sum=0;
    int length=length_L(L);
    while(p!=NULL)
    {
        sum+=p->data;
        p=p->next;
    }
    average=(float)sum/(length-1);
    return average;
}

void main()
{
    int i,get,length,e;
    LNode L;           //創建頭結點L
    L.next=NULL;
    do{
        printf("\n");
        printf("1.輸入數據元素，以先進先出形式創建單鏈表\n");
        printf("2.銷毀單鏈表\n");
        printf("3.線性表置空\n");
        printf("4.求線性表長度\n");
        printf("5.在第i個數據元素前插入新的元素\n");
        printf("6. 刪除第i個元素\n");
        printf("7.顯示線性表中的全部元素\n");
        printf("8.求最大元素的值和平均值\n");
        printf("9.退出\n");
        printf("請輸入你選擇的操作序號\n");
        scanf("%d",&get);
        switch(get){
             case 1:
                    printf("請輸入數據元素的個數\n");
                     scanf("%d",&length);
                    Create_List(&L,length);
                    break;
             case 2:
                     Destroy_L(&L);
                     break;
             case 3:
                     ClearList(&L);
                     break;
             case 4:
                 length=length_L(&L);
                 printf("這個線性鏈表的長度(含頭結點)為%d\n",length);
                 break;
             case 5:
                 printf("請分別輸入你要插入數據的元素的位置(第i個元素之前)和值(整型)\n");
                 scanf("%d,%d",&i,&e);
                 ListInsert(&L,i,&e);
                 break;
             case 6:
                 printf("請分別輸入你要刪除數據的元素的位置(第i個元素)\n");
                 scanf("%d",&i);
                 ListDelet(&L,i);
                 break;
             case 7:
                   length=length_L(&L);
                   display_all(&L,length);
                    break;
             case 8:
                   printf("線性表中的最大元素是%d\n",max_num(&L));
                   printf("線性表中所有元素的平均值%f\n",aver_num(&L));
                    break;
             case 9:
                 break;
        }
    }while(get!=9);
            
}