跑跑卡丁车手游官方网站

書名：數據結構與實訓
作者名：張紅霞白桂梅主編
本章字數： 1901字
更新時間： 2018-12-27 18:17:50

2.6 實訓例題

2.6.1 實訓例題1：有序順序表的建立及查找

【問題描述】

編寫算法，以輸入的整數序列（34,66,-21,73,84,-3,6,16）作為線性表各元素的值，創建一按元素值升序排列的順序表，并能對用戶的輸入值x給出是否在表中的判斷，若表中有此值，則將其刪除。

【基本要求】

對于輸入序列構造相應的順序表（升序排列），該過程涉及數據元素（在有序表中）的插入；對于用戶的輸入值x，給出是否在表中的判斷，此過程涉及表的查找；若表中有值x，則將其刪除，涉及順序表的刪除操作。

? 功能：

（1）初始化順序表；

（2）有序表的插入；

（3）在有序表中查找數據元素；

（4）刪除有序表的某一元素；

（5）輸出順序表各元素的值。

? 輸入：給定的整數序列（34,66,-21,73,84,-3,6,16）及要刪除的值。

? 輸出：順序表中（刪除指定值后）各元素的值。

【測試數據】

輸入（第一組）：34,66,-21,73,84,-3,6,16

要刪除的值：6

預期的輸出結果是：

-21 -3 6 16 34 66 73 84

及

-21 -3 16 34 66 73 84

輸入（第二組）：34,66,-21,73,84,-3,6,16

要刪除的值：18

預期的輸出結果是：

-21 -3 6 16 34 66 73 84

及

18 does not exit in the list.

-21 -3 6 16 34 66 73 84

【數據結構】

順序表的定義如下。

#define MaxSize 20
typedef struct seqlist
{ int elem[MAXSIZE];
  int listlength;
}SeqList;

【算法思想】

初始化順序表，循環輸入整數，并將其插入到有序順序表中，輸出順序表各元素的值。輸入要刪除的值，在有序表中查找該值，如果存在，則將其刪除，再次輸出順序表各元素的值。

【模塊劃分】

① 初始化順序表InitList。

② 將元素插入有序表InsList。

③ 在有序表中查找數據元素InList。

④ 刪除有序表的某一元素DelList。

⑤ 輸出順序表各元素的值Print。

⑥ 主函數main。

【源程序】

#define MaxSize 20
typedef struct seqlist
{ int  elem[MaxSize];
int  listlength;
}SeqList;
void InitList(SeqList *l) /*初始化順序表*/
{  l->listlength=0;
}/*InitList */
void Print(SeqList l) /*輸出順序表各元素的值*/
{  int i;
  for(i=0;i<l.listlength;++i)
      printf("%d ",l.elem[i]);
} /*Print*/
int InList(SeqList l,int x) /*在有序表中查找元素x */
{  int i=0;
   while (i<l.listlength && l.elem[i]<x)
        ++i;
   if (i<l.listlength)
       if(x==l.elem[i]) return (i);
   return (-1);
} /*InList*/
void InsList(SeqList *l,int x) /*將元素x插入有序表*/
{ int i=0,j;
  while (i<l->listlength && x>l->elem[i])
    i++;
  for(j=l->listlength-1;j>=i;--j)
     l->elem[j+1]=l->elem[j];
  l->elem[i]=x;
  (l->listlength)++;
}/*InsList*/
void DelList(SeqList *l,int i) /*刪除有序表的第i個元素*/
{ int j;
  if (i<0 || i>l->listlength-1)
  {  printf("\nIndex error ");
     return;
}
for(j=i+1;j<=l->listlength-1;++j)
        l->elem[j-1]=l->elem[j];
  l->listlength--;
}/*DelList */
main()
{  SeqList list;
     int index,element,x;
     InitList(&list);
     printf("Enter the first value in the list: ");
     scanf("%d",&element);
     printf("Enter the others in the list:");
     while(element!=0)
     {  InsList(&list,element);
          scanf("%d,",&element);
     }
     Print(list);
     printf("Enter the value to be deleted: ");
     scanf("%d",&x);
     index=InList(list,x);
     if(index==-1)
        printf("%d does not exit in the list. \n ",x);
     else
        DelList(&list,index);
     Print(list);
}/*main*/

【測試情況】

第一組數據：

Enter the first value in the list: 34

Enter the others in the list: 66,-21,73,84,-3,6,16,0

-21 -3 6 16 34 66 73 84

Enter the value to be deleted: 6

-21 -3 16 34 66 73 84

第二組數據：

Enter the first value in the list: 34

Enter the others in the list: 66,-21,73,84,-3,6,16,0

-21 -3 6 16 34 66 73 84

Enter the value to be deleted: 18

18 does not exit in the list.

-21 -3 6 16 34 66 73 84

【心得】

學生可以根據程序在計算機上調試運行，并結合自己在上機過程中遇到的問題和解決方法的體會，寫出調試分析過程、程序使用方法和測試結果，提交實訓報告。

2.6.2 實訓例題2：多項式的表示和相加

【問題描述】

在數學上，一個一元多項式Pn(x)可按升冪的形式寫成

Pn(x)=p0+p1x+p2x2+p3x3+…+pnxn

此多項式可以由n+1個系數唯一確定。因此，對應地可以用一個線性表P來表示

P=(p0,p1,p2,…,pn)

多項式中每項的指數就是相應系數的序號。

假設Qm(x)是一個一元多項式，則它也可以用一個線性表Q來表示，即

Q=(q0,q1,q2,…,qm)

若m<n，則兩個多項式相加的結果Rn(x)=Pn(x)+Qm(x)，也可以用線性表R來表示

R=(p0+q0,p1+q1,p2+q2,…,pm+qm,pm+1,…,pn)

問當多項式中存在大量的零系數時，是選擇順序存儲結構還是鏈式存儲結構？寫算法實現一元多項式的相加。

【基本要求】

對于線性表P、Q和R可以采用順序存儲結構，也可以采用鏈式存儲結構。使用順序存儲結構可以使多項式相加的算法十分簡單，即p[0]（q[0]）存儲系數p0（q0），p[1]（q[1]）存儲系數p1（q1）,…,p[n]（q[n]）存儲系數pn（qn），p、q對應單元的內容相加即可。但是，當多項式中存在大量的零系數時，這種表示方式就會浪費大量的存儲空間。因此，應采用鏈式存儲結構表示多項式，多項式中的每一個非零系數項構成鏈表中的一個結點（系數項和指數項），而對于系數為零的項則無須表示。

如圖2-16所示為兩個多項式的單鏈表，分別表示多項式A14(X)=9+6X+8X9+3X14與多項式B9(X)=7X+21X7-8X9。

圖2-16 單鏈表表示的多項式

? 功能：求兩個單鏈表表示的多項式的和。

? 輸入：兩個多項式每項的系數與指數。

? 輸出：和多項式的系數與指數。

【測試數據】

輸入：3,14 8,9 6,1 9,0與-8,9 21,7 7,1，預期的輸出是9,0 13,1 21,7 3,14。

【數據結構】

單鏈表結點、指針類型定義如下。

typedef struct PNode
{  int exp；         /*指數為整數*/
   float coef；      /*系數為實數*/
   struct PNode *next；
}PolyNode，*PolyList；

【算法思想】

多項式相加的原則是兩個多項式中所有指數相同的項的對應系數相加，若和不為零，則構成“和多項式”中的一項，所有指數不相同的項均復制到“和多項式”中。以單鏈表作為存儲結構，“和多項式”中的結點無須另外生成，可由多項式A、多項式B對應的單鏈表polya、polyb中的結點構成（和多項式鏈表可由polya指向）。

設pa、pb分別指向多項式A、B的一項（單鏈表polya、polyb中的一個結點），比較pa、pb所指結點的指數項，有如下3種情況。

（1）若pa->exp<pb->exp，則結點pa所指的結點應是“和多項式”中的一項，令指針pa后移。

（2）若pa->exp>pb->exp，則結點pb所指的結點應是“和多項式”中的一項，將pb所指結點插入在pa所指結點之前，且令指針pb在原來的鏈表上后移。

（3）若pa->exp=pb->exp，則將兩個結點中的系數相加，當和不為零時修改pa所指結點的系數域，釋放pb結點；若和為零，則和多項式中無此項，從A中刪去pa所指結點，同時釋放pa和pb所指的結點。

按以上運算規則對圖2-16表示的兩個多項式，得到的和多項式鏈表如圖2-17所示。其中孤立結點代表被釋放的結點。

圖2-17 運算后的“和多項式”

【模塊劃分】

① 建立帶頭結點的單鏈表Create，單鏈表是依指數升序排列的有序表，所輸入數據（系數，指數）是依指數為降序的序列。

② 求單鏈表polya與單鏈表polyb對應多項式的和PolyAdd。

③ 輸出單鏈表每個結點兩個數據域的值（多項式每項系數與指數）Print。

④ 主函數main，調用Create建立單鏈表polya，調用Create建立單鏈表polyb，調用PolyAdd求polya與polyb對應多項式的和，調用Print輸出和多項式每項的系數與指數（依指數升序）。

【源程序】

typedef struct PNode
{  int exp; /*指數為整數*/
   float coef;/*系數為實數*/
   struct PNode *next;
} PolyNode, *PolyList;
PolyList create()  /*建立帶頭結點的單鏈表*/
{
   PolyList h,p;
   float c;
   int e;
   h=(PolyList)malloc(sizeof(PolyNode));
   h->next=NULL;
   printf("\nEnter coef and exp:");
   scanf("%f,%d",&c,&e);/*輸入系數、指數*/
   while (e !=-1)
   {
     p=(PolyList)malloc(sizeof(PolyNode));
     p->coef=c;p->exp=e;
     p->next=h->next;
     h->next=p;
     printf("Enter coef and exp:");
     scanf("%f,%d",&c,&e);
   }
   return(h);
} /*create*/
void Print(PolyList h) /*輸出單鏈表的值*/
{
    PolyList p;
    p=h->next;
    printf("\n");
    while(p!=NULL)
    {
       printf("%g,%d ",p->coef,p->exp);
       p=p->next;
    }
}/*Print*/
void PolyAdd(PolyList polya,PolyList polyb) /*求單鏈表polya與polyb對應多項式的和*/
{
    PolyList pa,pb,pre,temp;/* pre指向和多項式鏈表的尾結點，temp 為臨時指針*/
    float sum;
    pa=polya->next;
    pb=polyb->next;
    pre=polya;
    while (pa!=NULL && pb!=NULL) /*當兩個多項式均未掃描結束時*/
    {
       if(pa->exp<pb->exp) /*將pa結點加入到和多項式中*/
       {
           pre->next=pa;
           epr=pre->next;
           pa=pa->next;
      }
      else if (pa->exp==pb->exp)   /*指數相同，則相應的系數相加*/
      {
         sum=pa->coef+pb->coef;
         if(sum!=0)
         {
             pa->coef=sum;
             pre->next=pa;pre=pre->next;
             pa=pa->next;
             temp=pb;pb=pb->next;free(temp);
         }
         else /*若系數和為零，則釋放pa和pb所指結點*/
         {
             temp=pa->next;free(pa);pa=temp;
             temp=pb->next;free(pb);pb=temp;
         }
      }
      else   /*將pb所指結點加入到和多項式中 */
      {
         pre->next=pb;pre=pre->next;
         pb=pb->next;
      }
   }
   if(pa!=NULL)    /*polya中還有剩余的結點*/
      pre->next=pa;
   else      /* polyb中還有剩余的結點*/
      pre->next=pb;
   free(polyb);
} /*PolyAdd */
main()
{
   PolyList pa,pb;
   pa=create();
   pb=create();
   PolyAdd(pa,pb);
   Print(pa);
}_/*main*/

【測試情況】

Enter coef and exp: 3,14

Enter coef and exp: 8,9

Enter coef and exp: 6,1

Enter coef and exp: 9,0

Enter coef and exp: -1,-1

Enter coef and exp:-8,9

Enter coef and exp: 21,7

Enter coef and exp: 7,1

Enter coef and exp: -1,-1

9,0 13,1 21,7 3,14

【心得】

官术网_书友最值得收藏!

數據結構與實訓

2.6 實訓例題

2.6.1 實訓例題1：有序順序表的建立及查找

2.6.2 實訓例題2：多項式的表示和相加