数据结构与算法分析--c语言描述(原书第二版)练习自答（第三章）(3.11~3.17)

3.11

list.h

#ifndef _List_H #define _List_H struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; typedef int ElementType; List MakeEmpty(List L); //List L is unused int IsEmpty(List L); int IsLast(Position P,List L); Position Find(ElementType X,List L); void Delete(ElementType X,List L); Position FindPrevious(ElementType X,List L); void Insert(ElementType X,List L,Position P); void DeleteList(List L); Position Header(List L); Position First(List L); Position Advance(Position P); ElementType Retrieve(Position P); void PrintList(List L); #endif

list_loop.c

#include <stdio.h> #include <stdlib.h> #include "list.h" struct Node { ElementType Element; Position Next; }; static void FataError(char *S); void FataError(char *S) { fputs("S\n",stderr); exit(EXIT_FAILURE); } /* Initiate a List,L is unused in this implementation */ List MakeEmpty(List L) { Position P; P=(Position)malloc(sizeof(struct Node)); P->Next=NULL; return P; } /* Return true if L is empty */ int IsEmpty(List L) { return L->Next==NULL; } /* Return true if P is the last position in List L,Parameter L is unused in this implementation */ int IsLast(Position P,List L) { return P->Next==NULL; } /* Return Position of X in L or NULL if not found */ Position Find(ElementType X,List L) { Position P; P=L->Next; while(P!=NULL&&P->Element!=X) P=P->Next; return P; } /* Delete first occurrence of X from a list */ void Delete(ElementType X,List L) { Position P,TmpCell; P=FindPrevious(X,L); if(!IsLast(P,L)) { TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } } /* If X is not found , the next field of returned Position is NULL */ Position FindPrevious(ElementType X,List L) { Position P; P=L; while(P->Next!=NULL&&P->Next->Element!=X) P=P->Next; return P; } /* Insert after legal position P,Parameter L is unused in this implementation */ void Insert(ElementType X,List L,Position P) { Position TmpCell; TmpCell=malloc(sizeof(struct Node)); if(TmpCell==NULL) FataError("Out of space!!"); TmpCell->Element=X; TmpCell->Next=P->Next; P->Next=TmpCell; } /* avoid delete header */ void DeleteList(List L) { Position P,Tmp; P=L->Next; L->Next=NULL; while(P!=NULL) { Tmp=P->Next; free(P); P=Tmp; } } /* Return header */ Position Header(List L) { return L; } /* Return the first node except header */ Position First(List L) { return L->Next; } /* Return the next node */ Position Advance(Position P) { return P->Next; } /* Return the select Element */ ElementType Retrieve(Position P) { return P->Element; } void PrintList(List L) { Position P; P=L->Next; if(IsEmpty(L)) FataError("List is empty!!!"); while(P!=NULL) { printf("%-5d",P->Element); P=P->Next; } }

list_recursive.c

#include <stdio.h> #include <stdlib.h> #include "list.h" struct Node { ElementType Element; Position Next; }; static void FataError(char *S); void FataError(char *S) { fputs("S\n",stderr); exit(EXIT_FAILURE); } /* Initiate a List,L is unused in this implementation */ List MakeEmpty(List L) { Position P; P=(Position)malloc(sizeof(struct Node)); P->Next=NULL; return P; } /* Return true if L is empty */ int IsEmpty(List L) { return L->Next==NULL; } /* Return true if P is the last position in List L,Parameter L is unused in this implementation */ int IsLast(Position P,List L) { return P->Next==NULL; } /* Return Position of X in L or NULL if not found */ Position Find(ElementType X,List L) { Position P; P=L->Next; if(P==NULL) return P; if(P->Element==X) return P; else Find(X,P); } /* Delete first occurrence of X from a list */ void Delete(ElementType X,List L) { Position P,TmpCell; P=FindPrevious(X,L); if(!IsLast(P,L)) { TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } } /* If X is not found , the next field of returned Position is NULL */ Position FindPrevious(ElementType X,List L) { Position P; P=L; while(P->Next!=NULL&&P->Next->Element!=X) P=P->Next; return P; } /* Insert after legal position P,Parameter L is unused in this implementation */ void Insert(ElementType X,List L,Position P) { Position TmpCell; TmpCell=malloc(sizeof(struct Node)); if(TmpCell==NULL) FataError("Out of space!!"); TmpCell->Element=X; TmpCell->Next=P->Next; P->Next=TmpCell; } /* avoid delete header */ void DeleteList(List L) { Position P,Tmp; P=L->Next; L->Next=NULL; while(P!=NULL) { Tmp=P->Next; free(P); P=Tmp; } } /* Return header */ Position Header(List L) { return L; } /* Return the first node except header */ Position First(List L) { return L->Next; } /* Return the next node */ Position Advance(Position P) { return P->Next; } /* Return the select Element */ ElementType Retrieve(Position P) { return P->Element; } void PrintList(List L) { Position P; P=L->Next; if(IsEmpty(L)) FataError("List is empty!!!"); while(P!=NULL) { printf("%-5d",P->Element); P=P->Next; } }

ceshi.c

#include <stdio.h> #include <stdlib.h> #include <time.h> #include "list.h" int main(void) { int Size,Target,i; srand((unsigned int)time(0)); Position P; List L; L=MakeEmpty(L); puts("The amount of the List:"); scanf("%d",&Size); P=L; for(i=0;i<Size;i++) { Insert(rand()%1000,L,P); P=Advance(P); } puts("The list is:"); PrintList(L); puts("List print done!"); putchar('\n'); fputs("which number do you want search:",stdout); scanf("%d",&Target); P=Find(Target,L); if(P!=NULL) printf("We find the target %d\n",Retrieve(P)); else puts("There is not match one!"); putchar('\n'); return 0; }

3.12

list.h

#ifndef _List_H #define _List_H struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; typedef int ElementType; List MakeEmpty(List L); //List L is unused int IsEmpty(List L); int IsLast(Position P,List L); Position Find(ElementType X,List L); void Delete(ElementType X,List L); Position FindPrevious(ElementType X,List L); void Insert(ElementType X,List L,Position P); void DeleteList(List L); Position Header(List L); Position First(List L); Position Advance(Position P); ElementType Retrieve(Position P); void PrintList(List L); List Reverse(List L); #endif

list_a.c

#include <stdio.h> #include <stdlib.h> #include "list.h" struct Node { ElementType Element; Position Next; }; static void FataError(char *S); void FataError(char *S) { fputs("S\n",stderr); exit(EXIT_FAILURE); } /* Initiate a List,L is unused in this implementation */ List MakeEmpty(List L) { Position P; P=(Position)malloc(sizeof(struct Node)); P->Next=NULL; return P; } /* Return true if L is empty */ int IsEmpty(List L) { return L->Next==NULL; } /* Return true if P is the last position in List L,Parameter L is unused in this implementation */ int IsLast(Position P,List L) { return P->Next==NULL; } /* Return Position of X in L or NULL if not found */ Position Find(ElementType X,List L) { Position P; P=L->Next; while(P!=NULL&&P->Element!=X) P=P->Next; return P; } /* Delete first occurrence of X from a list */ void Delete(ElementType X,List L) { Position P,TmpCell; P=FindPrevious(X,L); if(!IsLast(P,L)) { TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } } /* If X is not found , the next field of returned Position is NULL */ Position FindPrevious(ElementType X,List L) { Position P; P=L; while(P->Next!=NULL&&P->Next->Element!=X) P=P->Next; return P; } /* Insert after legal position P,Parameter L is unused in this implementation */ void Insert(ElementType X,List L,Position P) { Position TmpCell; TmpCell=malloc(sizeof(struct Node)); if(TmpCell==NULL) FataError("Out of space!!"); TmpCell->Element=X; TmpCell->Next=P->Next; P->Next=TmpCell; } /* avoid delete header */ void DeleteList(List L) { Position P,Tmp; P=L->Next; L->Next=NULL; while(P!=NULL) { Tmp=P->Next; free(P); P=Tmp; } } /* Return header */ Position Header(List L) { return L; } /* Return the first node except header */ Position First(List L) { return L->Next; } /* Return the next node */ Position Advance(Position P) { return P->Next; } /* Return the select Element */ ElementType Retrieve(Position P) { return P->Element; } void PrintList(List L) { Position P; P=L->Next; if(IsEmpty(L)) FataError("List is empty!!!"); while(P!=NULL) { printf("%-5d",P->Element); P=P->Next; } } List Reverse(List L) { List L1; Position P; P=L->Next; L1=MakeEmpty(L1); while(P!=NULL) { Insert(Retrieve(P),L1,L1); P=Advance(P); } return L1; }

list_b.c

#include <stdio.h> #include <stdlib.h> #include "list.h" struct Node { ElementType Element; Position Next; }; static void FataError(char *S); void FataError(char *S) { fputs("S\n",stderr); exit(EXIT_FAILURE); } /* Initiate a List,L is unused in this implementation */ List MakeEmpty(List L) { Position P; P=(Position)malloc(sizeof(struct Node)); P->Next=NULL; return P; } /* Return true if L is empty */ int IsEmpty(List L) { return L->Next==NULL; } /* Return true if P is the last position in List L,Parameter L is unused in this implementation */ int IsLast(Position P,List L) { return P->Next==NULL; } /* Return Position of X in L or NULL if not found */ Position Find(ElementType X,List L) { Position P; P=L->Next; while(P!=NULL&&P->Element!=X) P=P->Next; return P; } /* Delete first occurrence of X from a list */ void Delete(ElementType X,List L) { Position P,TmpCell; P=FindPrevious(X,L); if(!IsLast(P,L)) { TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } } /* If X is not found , the next field of returned Position is NULL */ Position FindPrevious(ElementType X,List L) { Position P; P=L; while(P->Next!=NULL&&P->Next->Element!=X) P=P->Next; return P; } /* Insert after legal position P,Parameter L is unused in this implementation */ void Insert(ElementType X,List L,Position P) { Position TmpCell; TmpCell=malloc(sizeof(struct Node)); if(TmpCell==NULL) FataError("Out of space!!"); TmpCell->Element=X; TmpCell->Next=P->Next; P->Next=TmpCell; } /* avoid delete header */ void DeleteList(List L) { Position P,Tmp; P=L->Next; L->Next=NULL; while(P!=NULL) { Tmp=P->Next; free(P); P=Tmp; } } /* Return header */ Position Header(List L) { return L; } /* Return the first node except header */ Position First(List L) { return L->Next; } /* Return the next node */ Position Advance(Position P) { return P->Next; } /* Return the select Element */ ElementType Retrieve(Position P) { return P->Element; } void PrintList(List L) { Position P; P=L->Next; if(IsEmpty(L)) FataError("List is empty!!!"); while(P!=NULL) { printf("%-5d",P->Element); P=P->Next; } } List Reverse(List L) { Position Current,NextPosition,Temp; if(L->Next!=NULL&&L->Next->Next!=NULL) { Current=L->Next; NextPosition=L->Next->Next; Current->Next=NULL; do { Temp=NextPosition->Next; NextPosition->Next=Current; Current=NextPosition; NextPosition=Temp; } while(NextPosition!=NULL); } L->Next=Current; return L; }

test.c

#include <stdio.h> #include "list.h" int main(void) { List L; Position P; ElementType i; L=MakeEmpty(L); P=L; fputs("Integer to insert list:",stdout); while(scanf("%d",&i)==1) { Insert(i,L,P); P=Advance(P); fputs("Continue(q to quit):",stdout); } PrintList(L); putchar('\n'); L=Reverse(L); PrintList(L); putchar('\n'); return 0; }

3.13

queue.h

#ifndef _Queue_H #define _Queue_H typedef int ElementType; struct QueueRecord; typedef struct QueueRecord *Queue; typedef struct QueueRecord *Position; int IsEmpty(Queue Q); Queue CreateQueue(void); void DisposeQueue(Queue Q); void MakeEmpty(Queue Q); void Enqueue(ElementType X,Queue Q); ElementType Front(Queue Q); void Dequeue(Queue Q); ElementType FrontAndDequeue(Queue Q); #endif

queue.c

#include <stdio.h> #include <stdlib.h> #include "queue.h" struct QueueRecord { int Size; Position Pre; Position Next; ElementType Element; }; static Position MakeNode(ElementType X); static void FatalError(char *str); static Position MakeNode(ElementType X) { Position Node; Node=malloc(sizeof(struct QueueRecord)); if(Node==NULL) FatalError("Not Enough Memory to create node!"); Node->Element=X; return Node; } static void FatalError(char *str) { fputs(str,stderr); putchar('\n'); exit(EXIT_FAILURE); } int IsEmpty(Queue Q) { return Q->Size==0; } Queue CreateQueue(void) { Queue Q; Q=malloc(sizeof(struct QueueRecord)); if(Q==NULL) FatalError("Not enough memory!"); Q->Size=0; Q->Pre=NULL; Q->Next=NULL; return Q; } void DisposeQueue(Queue Q) { while(!IsEmpty(Q)) Dequeue(Q); free(Q); } void MakeEmpty(Queue Q) { while(!IsEmpty(Q)) Dequeue(Q); } void Enqueue(ElementType X,Queue Q) { Position P; P=MakeNode(X); if(IsEmpty(Q)) { P->Pre=Q->Pre; P->Next=Q->Next; Q->Next=P; Q->Pre=P; Q->Size++; } else { Q->Next->Next=P; P->Pre=Q->Next; Q->Next=P; P->Next=NULL; Q->Size++; } } ElementType Front(Queue Q) { if(IsEmpty(Q)) puts("Queue is empty!"); else return Q->Pre->Element; } void Dequeue(Queue Q) { Position Temp; if(IsEmpty(Q)) puts("Queue is empty!"); else if(Q->Size==1) { Temp=Q->Pre; Q->Pre=NULL; Q->Next=NULL; Q->Size--; free(Temp); } else { Temp=Q->Pre; Q->Pre=Q->Pre->Next; Temp->Next->Pre=NULL; free(Temp); Q->Size--; } } ElementType FrontAndDequeue(Queue Q) { ElementType result; Position Temp; if(IsEmpty(Q)) puts("Queue is empty!"); else if(Q->Size==1) { Temp=Q->Pre; Q->Pre=NULL; Q->Next=NULL; Q->Size--; result=Temp->Element; free(Temp); return result; } else { Temp=Q->Pre; Q->Pre=Q->Pre->Next; Temp->Next->Pre=NULL; Q->Size--; result=Temp->Element; free(Temp); return result; } }

bucket.c

#include <stdio.h> #include "queue.h" #define Length 10 //数组长度 #define Times 3 //排序趟数 #define BucketNumber 1000 //桶的数量 void PrintArray(int array[],int N); void SortArray(int array[],int N); int main(void) { int array[]={123423435,876097312,764976102,284648038,837502984,105837087,381284439,510293402,847586023,625374612}; PrintArray(array,Length); putchar('\n'); SortArray(array,Length); PrintArray(array,Length); putchar('\n'); return 0; } void PrintArray(int array[],int N) { int i; for(i=0;i<N;i++) printf("%-12d",array[i]); } void SortArray(int array[],int N) { int divide,subnumber,subtime; int index; Queue Buckets[BucketNumber]; for(index=0;index<BucketNumber;index++) Buckets[index]=CreateQueue(); for(subtime=0,divide=1;subtime<Times;subtime++) { for(subnumber=0;subnumber<Length;subnumber++) { Enqueue(array[subnumber],Buckets[array[subnumber]/divide%BucketNumber]); } subnumber=0; for(index=0;index<BucketNumber;index++) { while(!IsEmpty(Buckets[index])) { array[subnumber]=FrontAndDequeue(Buckets[index]); subnumber++; } } divide*=BucketNumber; } }

3.15

a. list.h

#ifndef _List_H #define _List_H #define MaxLength 100 struct Node; typedef struct Node *List; typedef int Position; //start from 0 typedef int ElementType; List MakeEmpty(List L); int IsEmpty(List L); int IsLast(Position P,List L); Position Find(ElementType X,List L); void Delete(ElementType X,List L); void Insert(ElementType X,List L); void DeleteList(List L); Position First(List L); Position Advance(Position P); ElementType Retrieve(Position P,List L); void PrintList(List L); #endif

list.c

#include <stdio.h> #include <stdlib.h> #include "list.h" struct Node { ElementType *Array; int CurrentLength; }; static void FatalError(char *str); static void FatalError(char *str) { fputs(str,stderr); putchar('\n'); exit(EXIT_FAILURE); } List MakeEmpty(List L) { L=malloc(sizeof(struct Node)); if(L==NULL) FatalError("Haven't create list!"); L->Array=calloc(MaxLength,sizeof(ElementType)); if(L->Array==NULL) FatalError("Can't create the array inside list!"); L->CurrentLength=0; return L; } int IsEmpty(List L) { return L->CurrentLength==0; } int IsLast(Position P,List L) { return P==L->CurrentLength-1; } /*if find target ,return the index,or return -1 */ Position Find(ElementType X,List L) { ElementType Temp; int index,i; Position P=0; while(P<L->CurrentLength&&L->Array[P]!=X) P++; if(P==L->CurrentLength) return -1; else { Temp=L->Array[P]; for(i=P;i>0;i--) L->Array[i]=L->Array[i-1]; L->Array[0]=Temp; } return P; } void Delete(ElementType X,List L) { int index; Position P=0; while(P<L->CurrentLength&&L->Array[P]!=X) P++; if(P==L->CurrentLength) puts("Didn't have the element!"); else { for(index=P;index<L->CurrentLength-1;index++) L->Array[index]=L->Array[index+1]; L->CurrentLength--; } } void Insert(ElementType X,List L) { Position index; for(index=L->CurrentLength;index>0;index--) L->Array[index]=L->Array[index-1]; L->Array[0]=X; L->CurrentLength++; } void DeleteList(List L) { free(L->Array); free(L); } Position First(List L) { return 0; } Position Advance(Position P) { return P+1; } ElementType Retrieve(Position P,List L) { return L->Array[P]; } void PrintList(List L) { Position index; for(index=0;index<L->CurrentLength;index++) printf("]",L->Array[index]); putchar('\n'); }

test.c

#include <stdio.h> #include "list.h" int main(void) { List L; L=MakeEmpty(L); int i; fputs("integer for list:",stdout); while(scanf("%d",&i)==1) { Insert(i,L); } PrintList(L); while(getchar()!='\n') continue; fputs("integer to find:",stdout); scanf("%d",&i); Find(i,L); PrintList(L); return 0; }

b. list.h

#ifndef _List_H #define _List_H struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; typedef int ElementType; List MakeEmpty(List L); //List L is unused int IsEmpty(List L); int IsLast(Position P,List L); Position Find(ElementType X,List L); void Delete(ElementType X,List L); Position FindPrevious(ElementType X,List L); void Insert(ElementType X,List L); void DeleteList(List L); Position Header(List L); Position First(List L); Position Advance(Position P); ElementType Retrieve(Position P); void PrintList(List L); List Reverse(List L); #endif

list.c

#include <stdio.h> #include <stdlib.h> #include "list.h" struct Node { ElementType Element; Position Next; }; static void FataError(char *S); void FataError(char *S) { fputs("S\n",stderr); exit(EXIT_FAILURE); } /* Initiate a List,L is unused in this implementation */ List MakeEmpty(List L) { Position P; P=(Position)malloc(sizeof(struct Node)); P->Next=NULL; return P; } /* Return true if L is empty */ int IsEmpty(List L) { return L->Next==NULL; } /* Return true if P is the last position in List L,Parameter L is unused in this implementation */ int IsLast(Position P,List L) { return P->Next==NULL; } /* Return Position of X in L or NULL if not found */ Position Find(ElementType X,List L) { Position P; P=L->Next; while(P!=NULL&&P->Element!=X) P=P->Next; if(P!=NULL) { Delete(X,L); Insert(X,L); return L->Next; } else return P; } /* Delete first occurrence of X from a list */ void Delete(ElementType X,List L) { Position P,TmpCell; P=FindPrevious(X,L); if(!IsLast(P,L)) { TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } } /* If X is not found , the next field of returned Position is NULL */ Position FindPrevious(ElementType X,List L) { Position P; P=L; while(P->Next!=NULL&&P->Next->Element!=X) P=P->Next; return P; } /* Insert after legal position P,Parameter L is unused in this implementation */ void Insert(ElementType X,List L) { Position TmpCell; TmpCell=malloc(sizeof(struct Node)); if(TmpCell==NULL) FataError("Out of space!!"); TmpCell->Element=X; TmpCell->Next=L->Next; L->Next=TmpCell; } /* avoid delete header */ void DeleteList(List L) { Position P,Tmp; P=L->Next; L->Next=NULL; while(P!=NULL) { Tmp=P->Next; free(P); P=Tmp; } } /* Return header */ Position Header(List L) { return L; } /* Return the first node except header */ Position First(List L) { return L->Next; } /* Return the next node */ Position Advance(Position P) { return P->Next; } /* Return the select Element */ ElementType Retrieve(Position P) { return P->Element; } void PrintList(List L) { Position P; P=L->Next; if(IsEmpty(L)) FataError("List is empty!!!"); while(P!=NULL) { printf("%-5d",P->Element); P=P->Next; } } List Reverse(List L) { Position Current,NextPosition,Temp; if(L->Next!=NULL&&L->Next->Next!=NULL) { Current=L->Next; NextPosition=L->Next->Next; Current->Next=NULL; do { Temp=NextPosition->Next; NextPosition->Next=Current; Current=NextPosition; NextPosition=Temp; } while(NextPosition!=NULL); } L->Next=Current; return L; }

test.c

#include <stdio.h> #include "list.h" int main(void) { List L; L=MakeEmpty(L); int i; fputs("integer for list:",stdout); while(scanf("%d",&i)==1) { Insert(i,L); } PrintList(L); while(getchar()!='\n') continue; fputs("integer to find:",stdout); scanf("%d",&i); Find(i,L); PrintList(L); return 0; }

3.16

b. list.h

#ifndef _List_H #define _List_H struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; typedef int ElementType; List MakeEmpty(List L); //List L is unused int IsEmpty(List L); int IsLast(Position P,List L); Position Find(ElementType X,List L); void Delete(ElementType X,List L); Position FindPrevious(ElementType X,List L); void Insert(ElementType X,List L,Position P); void DeleteList(List L); Position Header(List L); Position First(List L); Position Advance(Position P); ElementType Retrieve(Position P); void PrintList(List L); void DeleteNode(Position P,List L); #endif

list.c

#include <stdio.h> #include <stdlib.h> #include "list.h" struct Node { ElementType Element; Position Next; }; static void FataError(char *S); void FataError(char *S) { fputs("S\n",stderr); exit(EXIT_FAILURE); } /* Initiate a List,L is unused in this implementation */ List MakeEmpty(List L) { Position P; P=(Position)malloc(sizeof(struct Node)); P->Next=NULL; return P; } /* Return true if L is empty */ int IsEmpty(List L) { return L->Next==NULL; } /* Return true if P is the last position in List L,Parameter L is unused in this implementation */ int IsLast(Position P,List L) { return P->Next==NULL; } /* Return Position of X in L or NULL if not found */ Position Find(ElementType X,List L) { Position P; P=L->Next; while(P!=NULL&&P->Element!=X) P=P->Next; return P; } /* Delete first occurrence of X from a list */ void Delete(ElementType X,List L) { Position P,TmpCell; P=FindPrevious(X,L); if(!IsLast(P,L)) { TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } } /* If X is not found , the next field of returned Position is NULL */ Position FindPrevious(ElementType X,List L) { Position P; P=L; while(P->Next!=NULL&&P->Next->Element!=X) P=P->Next; return P; } /* Insert after legal position P,Parameter L is unused in this implementation */ void Insert(ElementType X,List L,Position P) { Position TmpCell; TmpCell=malloc(sizeof(struct Node)); if(TmpCell==NULL) FataError("Out of space!!"); TmpCell->Element=X; TmpCell->Next=P->Next; P->Next=TmpCell; } /* avoid delete header */ void DeleteList(List L) { Position P,Tmp; P=L->Next; L->Next=NULL; while(P!=NULL) { Tmp=P->Next; free(P); P=Tmp; } } /* Return header */ Position Header(List L) { return L; } /* Return the first node except header */ Position First(List L) { return L->Next; } /* Return the next node */ Position Advance(Position P) { return P->Next; } /* Return the select Element */ ElementType Retrieve(Position P) { return P->Element; } void PrintList(List L) { Position P; P=L->Next; if(IsEmpty(L)) FataError("List is empty!!!"); while(P!=NULL) { printf("%-5d",P->Element); P=P->Next; } } void DeleteNode(Position P,List L) { Position Current; Current=L; while(Current->Next!=NULL&&Current->Next!=P) Current=Advance(Current); Current->Next=P->Next; free(P); }

deleteduplicate.c

#include <stdio.h> #include "list.h" int main(void) { Position P1,P2,Temp; List L; L=MakeEmpty(L); Temp=L; int i; fputs("integer for list:",stdout); while(scanf("%d",&i)==1) { Insert(i,L,Temp); Temp=Advance(Temp); } PrintList(L); while(getchar()!='\n') continue; for(P1=Advance(L);Advance(P1)!=NULL;P1=Advance(P1)) //from line 19 to 33 is the implementation { P2=Advance(P1); while(P2!=NULL) { if(Retrieve(P1)==Retrieve(P2)) { Temp=P2; P2=Advance(P2); DeleteNode(Temp,L); } else P2=Advance(P2); } } PrintList(L); return 0; }

c. list.h

#ifndef _List_H #define _List_H #define MaxLength 100 struct Node; typedef struct Node *List; typedef int Position; //start from 0 typedef int ElementType; List MakeEmpty(List L); int IsEmpty(List L); int IsLast(Position P,List L); Position Find(ElementType X,List L); void Delete(ElementType X,List L); void Insert(ElementType X,List L); void DeleteList(List L); Position First(List L); Position Advance(Position P); ElementType Retrieve(Position P,List L); void PrintList(List L); #endif

list.c

#include <stdio.h> #include <stdlib.h> #include "list.h" struct Node { ElementType *Array; int CurrentLength; }; static void FatalError(char *str); static void FatalError(char *str) { fputs(str,stderr); putchar('\n'); exit(EXIT_FAILURE); } List MakeEmpty(List L) { L=malloc(sizeof(struct Node)); if(L==NULL) FatalError("Haven't create list!"); L->Array=calloc(MaxLength,sizeof(ElementType)); if(L->Array==NULL) FatalError("Can't create the array inside list!"); L->CurrentLength=0; return L; } int IsEmpty(List L) { return L->CurrentLength==0; } int IsLast(Position P,List L) { return P==L->CurrentLength-1; } /*if find target ,return the index,or return -1 */ Position Find(ElementType X,List L) { ElementType Temp; int index,i; Position P=0; while(P<L->CurrentLength&&L->Array[P]!=X) P++; if(P==L->CurrentLength) return -1; else { Temp=L->Array[P]; for(i=P;i>0;i--) L->Array[i]=L->Array[i-1]; L->Array[0]=Temp; } return P; } void Delete(ElementType X,List L) { int index; Position P=0; while(P<L->CurrentLength&&L->Array[P]!=X) P++; if(P==L->CurrentLength) puts("Didn't have the element!"); else { for(index=P;index<L->CurrentLength-1;index++) L->Array[index]=L->Array[index+1]; L->CurrentLength--; } } void Insert(ElementType X,List L) { Position index; for(index=L->CurrentLength;index>0;index--) L->Array[index]=L->Array[index-1]; L->Array[0]=X; L->CurrentLength++; } void DeleteList(List L) { free(L->Array); free(L); } Position First(List L) { return 0; } Position Advance(Position P) { return P+1; } ElementType Retrieve(Position P,List L) { return L->Array[P]; } void PrintList(List L) { Position index; for(index=0;index<L->CurrentLength;index++) printf("]",L->Array[index]); putchar('\n'); }

deleteduplicate.c

#include <stdio.h> #define Length 9 int DeleteDuplicate(int arr[],int N); int main(void) { int index,currentlength; int array[]={1,2,3,4,5,3,4,2,6}; for(index=0;index<Length;index++) printf("]",array[index]); putchar('\n'); currentlength=Length-DeleteDuplicate(array,Length); for(index=0;index<currentlength;index++) printf("]",array[index]); putchar('\n'); return 0; } int DeleteDuplicate(int arr[],int N) { int count=0; int index_outside,index_inside,index_temp; for(index_outside=0;index_outside<N;index_outside++) { for(index_inside=index_outside+1;index_inside<N;) { if(arr[index_outside]==arr[index_inside]) { for(index_temp=index_inside;index_temp<N-1;index_temp++) arr[index_temp]=arr[index_temp+1]; N-=1; count++; } else index_inside++; } } return count; }

3.17

list.h

#ifndef _List_H #define _List_H struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; typedef int ElementType; List MakeEmpty(List L); int IsEmpty(List L); int CountList(List L); void DeleteNode(Position P,List L); Position Find(ElementType X,List L); void PrintList(List L); void Insert(ElementType X,List L,Position P); void LazyDelete(ElementType X,List L); /*the part below this line haven't been modified*/ int IsLast(Position P,List L); void Delete(ElementType X,List L); Position FindPrevious(ElementType X,List L); void DeleteList(List L); Position Header(List L); Position First(List L); Position Advance(Position P); ElementType Retrieve(Position P); #endif

list.c

#include <stdio.h> #include <stdlib.h> #include "list.h" struct Node { ElementType Element; Position Next; int Num;/*in the header the element is the amount of the deleted nodes.in the other node this element is the lazy deletion bit,0 as deleted,1 as haven't be deleted.*/ }; static void FataError(char *S); void FataError(char *S) { fputs("S\n",stderr); exit(EXIT_FAILURE); } /* Initiate a List,L is unused in this implementation */ List MakeEmpty(List L) { Position P; P=(Position)malloc(sizeof(struct Node)); P->Next=NULL; P->Num=0; return P; } /* Return true if L is empty */ int IsEmpty(List L) { if(CountList(L)-L->Num==0) return 1; return 0; } int CountList(List L) { int count=0; Position P; P=L->Next; while(P!=NULL) { P=Advance(P); count++; } return count; } void DeleteNode(Position P,List L) { Position Current; Current=L; while(Current->Next!=NULL&&Current->Next!=P) Current=Advance(Current); Current->Next=P->Next; L->Num--; free(P); } void LazyDelete(ElementType X,List L) { Position P; if(L->Num>=(CountList(L)/2)) { P=L->Next; while(P!=NULL) { if(P->Num==0) DeleteNode(P,L); } } else { P=Find(X,L); P->Num=0; } } /* Return Position of X in L or NULL if not found */ Position Find(ElementType X,List L) { Position P; P=L->Next; while(P!=NULL&&P->Element!=X) { a:P=P->Next; } if(P->Num==0) goto a; return P; } void PrintList(List L) { Position P; P=L->Next; if(IsEmpty(L)) FataError("List is empty!!!"); while(P!=NULL) { if(P->Num!=0) { printf("%-5d",P->Element); } P=P->Next; } } void Insert(ElementType X,List L,Position P) { Position TmpCell; TmpCell=malloc(sizeof(struct Node)); if(TmpCell==NULL) FataError("Out of space!!"); TmpCell->Element=X; TmpCell->Num=1; TmpCell->Next=P->Next; P->Next=TmpCell; } /*the part below this line haven't been modified*/ int IsLast(Position P,List L) { return P->Next==NULL; } void Delete(ElementType X,List L) { Position P,TmpCell; P=FindPrevious(X,L); if(!IsLast(P,L)) { TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } } Position FindPrevious(ElementType X,List L) { Position P; P=L; while(P->Next!=NULL&&P->Next->Element!=X) P=P->Next; return P; } void DeleteList(List L) { Position P,Tmp; P=L->Next; L->Next=NULL; while(P!=NULL) { Tmp=P->Next; free(P); P=Tmp; } } Position Header(List L) { return L; } Position First(List L) { return L->Next; } Position Advance(Position P) { return P->Next; } ElementType Retrieve(Position P) { return P->Element; }

test.c

#include <stdio.h> #include "list.h" int main(void) { Position P; List L; L=MakeEmpty(L); int i; P=L; fputs("integer for list:",stdout); while(scanf("%d",&i)==1) { Insert(i,L,P); P=Advance(P); } PrintList(L); while(getchar()!='\n') continue; fputs("integer to delete:",stdout); while(scanf("%d",&i)==1) { LazyDelete(i,L); PrintList(L); putchar('\n'); } PrintList(L); return 0; }