第2章线性表 要求: 1、掌握线性表的逻辑结构; 2、线性表的顺序存储表示及其算法 3、线性表的链式存储表示及其算法; 教材习题参考解答: 2.1略 2.2(1)n/2与(mn=1)/2n (2)也(一定) (3)LL>next上二元素结点的指针域指示。 2.3a4,1 b7,11,8,4,c5,12d11,9,6,1或11,9,13,1或11,9,1,6 2.4/*P49习题2.4示例程序* #define maxsize 100 typedef int ElemType; typedef struct ElemType elem[Maxsize] int last JSlIst int InsertList (SqList *pL, ElemType x) int k if(pL->last>=Maxsize-1) return(0) k=pL->last *k>=0保证线形表不为空,pL->elem[k]>x保证插入位置正确*/ while((k>=0)&&(pL->elem[k]>x)) pL->elem[k+1]=pL->elem[k] pL->elem[k+1]=x L-last++ return (1) id ElemType e Sqlist l;/*定义线形表变量*/
第 2 章 线性表 要求： 1、 掌握线性表的逻辑结构； 2、 线性表的顺序存储表示及其算法； 3、 线性表的链式存储表示及其算法； 教材习题参考解答： 2.1 略 2.2 (1)n/2 与(n-1)/2 n (2)也(一定) 不一定 (3)L L->next 上一元素结点的指针域指示。 2.3 a 4,1 b 7,11,8,4,1 c 5,12 d 11,9,6,1 或 11,9,13,1 或 11,9,1,6 2.4 /*P49 习题 2.4 示例程序 */ #define Maxsize 100 typedef int ElemType; typedef struct { ElemType elem[Maxsize]; int last; }SqList; int InsertList(SqList *pL,ElemType x) { int k; if(pL->last>=Maxsize-1) return (0); k=pL->last; /*k>=0 保证线形表不为空,pL->elem[k]>x 保证插入位置正确*/ while((k>=0) && (pL->elem[k] > x)) { pL->elem[k+1]=pL->elem[k]; k--; } pL->elem[k+1]=x; pL->last++; return (1); } void main() { int i; ElemType e; SqList L; /*定义线形表变量*/
L.1ast=1;/*置线形表为空表状态*/ 任意输入10个整数*/ or(i=0;i #define maxsize 100 typedef int ElemType typedef struct Elem Type elem [Maxsize] JSlIst int DelElem(SqList apL, int i, int k) /*判断i和k的值的合法性*/ if(ipL->last+1) return(O) (i=i+k-1: jelem[j-k]=pL->elem [j] pL-last-=k return(1) void Print(sqlist *pL) for (i=0; ilast: i++) printf( %d\t", pL->elem[il) Sqlist l;/*定义线形表变量*/
L.last=-1; /*置线形表为空表状态*/ /*任意输入 10 个整数*/ for(i=0;i #define Maxsize 100 typedef int ElemType; typedef struct { ElemType elem[Maxsize]; int last; }SqList; int DelElem(SqList *pL,int i,int k) { int j; /*判断 i 和 k 的值的合法性*/ if(ipL->last+1) return(0); for(j=i+k-1;jlast;j++) pL->elem[j-k]=pL->elem[j]; pL->last-=k; return(1); } void Print(SqList *pL) { int i; for(i=0;ilast;i++) printf("%d\t",pL->elem[i]); printf("\n"); } void main() { int i,k; SqList L; /*定义线形表变量*/
L.1ast=-1;/*置线形表为空表状态*/ /*向线形表中顺序存入1-20*/ for(i=0;i #define null o typedef int elemType: typedef struct node data struct node水next }Node,米 Linklist /*初始化带头结点的单链表*/ void InitList(LinkList *pL) *pL=(LinkList)malloc(sizeof ( node)) (*pL)->next=NULL /*头插法插入元素*/ void InsertList(LinkList L, ElemType e) Linklist p: p=(LinkList)malloc(sizeof (Node)) L->next=p void shanchu(LinkList L, int mink, int maxk) //让指针p指向第一个元素比mink大的结点,q指向p前面的结点
L.last=-1; /*置线形表为空表状态*/ /*向线形表中顺序存入 1-20*/ for(i=0;i #include #define NULL 0 typedef int ElemType; typedef struct node { ElemType data; struct node *next; }Node,*LinkList; /*初始化带头结点的单链表*/ void InitList(LinkList *pL) { *pL=(LinkList)malloc(sizeof(Node)); (*pL)->next=NULL; } /*头插法插入元素*/ void InsertList(LinkList L,ElemType e) { LinkList p; p=(LinkList)malloc(sizeof(Node)); p->data=e; p->next=L->next; L->next=p; } void shanchu(LinkList L, int mink, int maxk) { LinkList p,q; q = L; p = L->next; //让指针 p 指向第一个元素比 mink 大的结点，q 指向 p 前面的结点
while(p! = NULL & p->data next //删除所有比mink大比maxk小的结点 while(p ! NULL & p->data maxk) g->next p->nex free(p) p=g->next void Print(LinkList L) LinkList p: for(p L->next; p!= NULL p= p->next) printf(%d\t", p->data) printf("\n") void maino InitList(&L) /*初始化链表*/ /*向线形表中顺序存入1-20*/ for(i=10;i>0;i一) InsertList(L, i Print (l) /*将原结果输出*/ shanchu(L,6,9);/将大于6小于9地元素删除 /*将逆置后结果输出*/ 2.7/*P49习题2.71示例程序* /*采用顺序存储方法进行线形表的逆置*/ #include <stdio. h #define maxsize 100 typedef int ElemType typedef struct ElemType elem [Maxsize int last I Sqlist void Nizhi(SqList *pL)
while(p != NULL && p->data next; } //删除所有比 mink 大比 maxk 小的结点 while(p != NULL && p->data next = p->next; free(p); p = q->next; } } void Print(LinkList L) { LinkList p; for(p = L->next; p != NULL; p = p->next) printf("%d\t",p->data); printf("\n"); } void main() { int i; LinkList L; InitList(&L); /*初始化链表*/ /*向线形表中顺序存入 1-20*/ for(i=10; i>0; i--) InsertList(L,i); Print(L); /*将原结果输出*/ shanchu(L, 6, 9); //将大于 6 小于 9 地元素删除 Print(L); /*将逆置后结果输出*/ } 2.7 /*P49 习题 2.71 示例程序 */ /*采用顺序存储方法进行线形表的逆置*/ #include #define Maxsize 100 typedef int ElemType; typedef struct { ElemType elem[Maxsize]; int last; }SqList; void Nizhi(SqList *pL)
ElemType temp: Int j=pL->last while(ielem[i] pL->elem[i]=pL->elem[j] pL->elem [j]=temp 1++ void Print (Sqlist *pL) for(i=0: ilast; i++) printf(%d\t", pL->elem[i]) printf( "\n") void maino Int 1 Sqlist L;/*定义线形表变量*/ L.last=-1;/*置线形表为空表状态*/ /*向线形表中顺序存入1-20*/ for(i=0;i #include #define null o typedef int ElemType typedef struct node ElemType data
{ ElemType temp; int i,j; i=0; j=pL->last; while(ielem[i]; pL->elem[i]=pL->elem[j]; pL->elem[j]=temp; i++; j--; } } void Print(SqList *pL) { int i; for(i=0;ilast;i++) printf("%d\t",pL->elem[i]); printf("\n"); } void main() { int i; SqList L; /*定义线形表变量*/ L.last=-1; /*置线形表为空表状态*/ /*向线形表中顺序存入 1-20*/ for(i=0;i #include #define NULL 0 typedef int ElemType; typedef struct node { ElemType data;
struct node next I Node, *LinkList /*初始化带头结点的单链表* void InitList(LinkList *pL) *pL=(LinkList)malloc(sizeof (node)) (=*pL)->next=NULL /*头插法插入元素*/ void InsertList (LinkList L, ElemType e) Linklist p: p=(LinkList)malloc(sizeof (Node)) p->data=e p->next=L->next void Nizhi(linkList L) Linklist p, g,w p=L->next /*将原来的第一个结点变为最后一个*/ if(p != NULL) p->next=NULL >next L->next=p void Print(LinkList L) Linklist for(p= L->next: p!= NULL p= p->next) printf("%d\t", p->data) rinf("Ⅶn"); id maino
struct node *next; }Node,*LinkList; /*初始化带头结点的单链表*/ void InitList(LinkList *pL) { *pL=(LinkList)malloc(sizeof(Node)); (*pL)->next=NULL; } /*头插法插入元素*/ void InsertList(LinkList L,ElemType e) { LinkList p; p=(LinkList)malloc(sizeof(Node)); p->data=e; p->next=L->next; L->next=p; } void Nizhi(LinkList L) { LinkList p,q,w; p=L->next; /*将原来的第一个结点变为最后一个*/ if(p != NULL) { q=p->next; p->next=NULL; } while(q != NULL) { w=q->next; q->next=p; p=q; q=w; } L->next=p; } void Print(LinkList L) { LinkList p; for(p = L->next; p != NULL; p = p->next) printf("%d\t",p->data); printf("\n"); } void main()
netlist(&L);/*初始化链表*/ /*向线形表中顺序存入1-20*/ for(i=0;i #include #define null o typedef int ElemType typedef struct node data I Nod /*初始化带头结点的单链表*/ void InitList(LinkList *pL) *pL=(LinkList)malloc(sizeof ( node)) (=*pL)->next=NULL /*向递增有序的线性表中插入元素,插入后仍递增有序* void InsertList(LinkList L, ElemType e) p=(LinkList)malloc(sizeof (Node)) q while(g->next ! NULL & g>next->data e) g= g>next: g->next=p //归并LA和LB到LC中 void Guibing(linkList LA, LinkList LB, LinkList LC) Linklist
{ int i; LinkList L; InitList(&L); /*初始化链表*/ /*向线形表中顺序存入 1-20*/ for(i=0;i #include #define NULL 0 typedef int ElemType; typedef struct node { ElemType data; struct node *next; }Node,*LinkList; /*初始化带头结点的单链表*/ void InitList(LinkList *pL) { *pL=(LinkList)malloc(sizeof(Node)); (*pL)->next=NULL; } /*向递增有序的线性表中插入元素，插入后仍递增有序*/ void InsertList(LinkList L,ElemType e) { LinkList p, q; p=(LinkList)malloc(sizeof(Node)); p->data=e; q = L; while(q->next != NULL && q->next->data next; p->next=q->next; q->next=p; } //归并 LA 和 LB 到 LC 中 void Guibing(LinkList LA, LinkList LB, LinkList LC) { LinkList p, q, t; p = LA->next;
while(p null & q!= NULL if(p->data q->data t= p: els t->next=LC->next;//将t所指结点插入LC头结点之后 LC->next = t LB->next NULL void Print(linkList L) for(p L->next: p != NULL: p= p->next) printf("%d\t", p->data) printf("\n") id mainO Linklist la, lb, lc InitList(&LA) /*初始化链表*/ InitList(&LB) Initlist(&LC) /*向线形表LA中按递增有序地插入5个数*/ printf("请输入第%个数:",i+1) InsertList(LA, e) Print (lay /*将LA输出*/ /*向线形表LA中按递增有序地插入5个数*/
q = LB->next; while(p != NULL && q != NULL) { if(p->data data) { t = p; p = p->next; } else { t = q; q = q->next; } t->next = LC->next;//将 t 所指结点插入 LC 头结点之后 LC->next = t; } LA->next = NULL; LB->next = NULL; } void Print(LinkList L) { LinkList p; for(p = L->next; p != NULL; p = p->next) printf("%d\t",p->data); printf("\n"); } void main() { int i, e; LinkList LA, LB, LC; InitList(&LA); /*初始化链表*/ InitList(&LB); InitList(&LC); /*向线形表 LA 中按递增有序地插入 5 个数*/ for(i=0; i<5; i++) { printf("请输入第 %d 个数：",i+1); scanf("%d",&e); InsertList(LA,e); } Print(LA); /*将 LA 输出*/ /*向线形表 LA 中按递增有序地插入 5 个数*/ for(i=0; i<5; i++)
printf("请输入第‰个数:",i+1) scanf(%d", &e) InsertList(LB, e) Print (lB) /*将LA输出* Guibing(LA, LB, Lc) //将大于6小于9地元素删除 Print(lc) /*将逆置后结果输出*/ 2.9/*P49习题2.8示例程序* #include #include #define null o typedef int ElemType: typedef struct node ElemType data struct node * next }Node,米 Linklist *向环行链表中插入元素*/ void Insertlist (linklist *ph, ElemType e) p=(LinkList)malloc(sizeof (Node)) >data=e if(pH = NULL) e p->next =(*pH)->next (*pH)->next p //删除H所指结点的前一个结点 void Delete (linkList H, int *pe f(H->next==H)//若环行链表中只有一个结点,则返回 return
{ printf("请输入第 %d 个数：",i+1); scanf("%d",&e); InsertList(LB,e); } Print(LB); /*将 LA 输出*/ Guibing(LA, LB, LC); //将大于 6 小于 9 地元素删除 Print(LC); /*将逆置后结果输出*/ } 2.9 /*P49 习题 2.8 示例程序 */ #include #include #define NULL 0 typedef int ElemType; typedef struct node { ElemType data; struct node *next; }Node,*LinkList; /*向环行链表中插入元素*/ void InsertList(LinkList *pH,ElemType e) { LinkList p; p=(LinkList)malloc(sizeof(Node)); p->data=e; if(*pH == NULL) { p->next = p; *pH = p; } else { p->next = (*pH)->next; (*pH)->next = p; } } //删除 H 所指结点的前一个结点 void Delete(LinkList H, int *pe) { LinkList p, t; if(H->next == H) //若环行链表中只有一个结点，则返回 return;
p->next = t->next //或者p>next free(t) //将环行链表输出 void Print(linkList H) Linklist f(H = NULL return (p=H: p->next =H; p printf(" %d\t", p->data) printf( %d\n", p->data) id mainO Linklist h: H E NULL. //初始化无头结点的环行链表 /*向环行表H中输入5个 for(i=0;i #include ine null o typedef int elemType: dat struct node next
for(p = H; p->next->next != H; p = p->next); t = p->next; p->next = t->next; //或者 p->next = H *pe = t->data; free(t); } //将环行链表输出 void Print(LinkList H) { LinkList p; if(H == NULL) return; for(p = H; p->next != H; p = p->next) printf("%d\t",p->data); printf("%d\n",p->data); } void main() { int i, e; LinkList H; H = NULL; //初始化无头结点的环行链表 /*向环行表 H 中输入 5 个数*/ for(i=0; i #include #define NULL 0 typedef int ElemType; typedef struct node { ElemType data; struct node *next;
