📄 习题11-单链表（综合练习）.c

📁 数据结构各章实验源代码；数据结构实验源代码
💻 C
字号:
#include  "datastru.h"
#include  <stdio.h>
#include  <malloc.h>

int locate(LINKLIST *a,char x)
/*检查元素x是否在a表中*/
{LINKLIST *la;

la = a->next;
while(la !=NULL)
   if(la->data == x) return 1;
   else la = la->next;
return 0;
}

insert(LINKLIST *a,char x)
/*将x元素加入a表中*/
{LINKLIST *p;

p = (LINKLIST *) malloc(sizeof(LINKLIST));
p->data = x;
p->next = a->next;
a->next = p;
}

void unionn(LINKLIST *a1, LINKLIST *b1){
/*两有序表交集*/
LINKLIST *lb;

lb = b1->next;
while(lb != NULL)
 { if (!locate(a1,lb->data))   /*如果b1表中的一个元素不在a1表中*/
    insert(a1,lb->data);       /*则将b1表中的该元素加入a1表中*/
   lb = lb->next;}
}

void unite(LINKLIST *a, LINKLIST *b, LINKLIST *c){
/*a, b为两有序链表，合并到c表，并保持有序*/
LINKLIST *la, *lb, *lc, *p;

la = a->next; lb = b->next; lc = c;
while(la != NULL && lb != NULL)
 { if (la->data <= lb->data)
    { p = (LINKLIST *) malloc(sizeof(LINKLIST));
      p->data = la->data;   p->next = NULL;
      lc->next = p;   lc = lc->next;   la = la->next;
    }
   else
    { p = (LINKLIST *) malloc(sizeof(LINKLIST));
      p->data = lb->data;   p->next = NULL;
      lc->next = p;   lc = lc->next;   lb = lb->next;
    }
 }
 while(la != NULL)
 {  p = (LINKLIST *) malloc(sizeof(LINKLIST));
    p->data = la->data;   p->next = NULL;
    lc->next = p;   lc = lc->next;  la = la->next;
 }
while(lb != NULL)
 {  p = (LINKLIST *) malloc(sizeof(LINKLIST));
    p->data = lb->data;   p->next = NULL;
    lc->next = p;   lc = lc->next;   lb = lb->next;
 }
}

void delete1(LINKLIST *a){
/*无序链表中删除重复元素，重复元素保留一个*/
LINKLIST *la, *p, *q;

la = a->next;
while(la != NULL)
 { q = la; p = la->next;
   while(p != NULL)
     {if (p->data == la->data)
       { p = p->next; q->next = p;}
      else { q = p; p = p->next;}
     }
   la = la->next;
 }
}

void delete(LINKLIST *a){
/*有序链表中删除重复元素，重复元素保留一个*/
LINKLIST *la;

la = a->next;
while(la != NULL && la->next != NULL)
 if (la->data == la->next->data)
    la->next = la->next->next;
 else la = la->next;
}

inser_order(DATATYPE2 x, LINKLIST *head){
/*有序表中插入元素x,并保持表有序*/
  LINKLIST *pr, *pn, *pp;

  pr = head; pn = head->next;
  while(pn != NULL && pn->data < x)
   {pr = pn;
    pn = pn->next;}
  pp = (LINKLIST *)malloc(sizeof(LINKLIST));
  pp->data = x;
  pp->next = pr->next;
  pr->next = pp;
}

LINKLIST *invertlink(LINKLIST *head){
/*单链表元素逆置*/
  LINKLIST *p, *q, *r;

  q = NULL;  p = head;
  while(p != NULL)
     {r = q; q = p ;
      p = p->next;
	  q->next = r;}
  return q;
}

int count_nohead(LINKLIST *head){
/*不带头结点的单链表：输出单链表元素值并计数*/
  int i = 0;
  LINKLIST *p;
  p = head;
  printf("输出单链表元素值 : ");
  while(p != NULL)
   {printf("  %c",p->data);
    i++;
    p = p->next;}
  printf("\n");
  return i;
}

int count_head(LINKLIST *head){
/*带头结点的单链表：输出单链表元素值并计数*/
  int i = 0;
  LINKLIST *p;
  p = head->next;
  printf("输出单链表元素值 : ");
  while(p != NULL)
   {printf("  %c",p->data);
    i++;
    p = p->next;}
  printf("\n");
  return i;
}

LINKLIST *creatlink_nohead_head(LINKLIST *head) {
/*用头插入法建立不带头结点的单链表*/
	LINKLIST  *t;
  char ch;

  printf("单链表元素值为单个字符, 连续输入，$为结束字符  : ");
  while((ch = getchar())!= '$')
   {	t = (LINKLIST *) malloc(sizeof(LINKLIST));
	    t->data = ch;
	    t->next = head;
        head = t;}
return(head);
}

LINKLIST *creatlink_head_head(LINKLIST *head) {
/*用头插入法建立带头结点的单链表*/
  LINKLIST  *t;
  char ch;

  t = (LINKLIST *)malloc(sizeof(LINKLIST));
  head = t;
  t->next = NULL;
  printf("单链表元素值为单个字符, 连续输入，$为结束字符  : ");
  while((ch = getchar())!= '$')
   {t = (LINKLIST *) malloc(sizeof(LINKLIST));
    t->data = ch;
    t->next = head->next;
    head->next = t;}
  return(head);
}

LINKLIST *creatlink_nohead_rail(LINKLIST *head){
/*用尾插入法建立不带头结点的单链表*/
  LINKLIST *last, *t;
  char ch;

  last = head;
  printf("单链表元素值为单个字符, 连续输入，$为结束字符  : ");
  while ((ch = getchar()) != '$')
   {t = (LINKLIST *)malloc(sizeof(LINKLIST));
    t->data = ch;
    t->next = NULL;
    if (head == NULL) {head = t; last = t;}
    else { last->next = t; last = t;}
  }
  return (head);
}

LINKLIST *creatlink_head_rail(LINKLIST *head){
/*用尾插入法建立带头结点的单链表*/
  LINKLIST *last, *t;
  char ch;
  
  t = (LINKLIST *)malloc(sizeof(LINKLIST));
  head = t;  last = t;
  t->next = NULL;
  printf("单链表元素值为单个字符, 连续输入，$为结束字符  : ");
  while ((ch = getchar()) != '$')
   {t = (LINKLIST *)malloc(sizeof(LINKLIST));
    t->data = ch;
    t->next = NULL;
    last->next = t;
    last = t;}
  return (head);
}

LINKLIST *creatlink_order_head(LINKLIST *head)
/*建立带头结点的有序单链表*/
{ LINKLIST *t, *p, *q;
  char ch;

  t = (LINKLIST *)malloc(sizeof(LINKLIST));
  head = t;  t->next = NULL;
  printf("单链表元素值为单个字符, 连续输入，$为结束字符  : ");
  while ((ch = getchar()) != '$')
   {t = (LINKLIST *)malloc(sizeof(LINKLIST));
    t->data = ch;
    q = head;  p = head->next;
    while( p != NULL && p->data <= ch) {
	q = p;  p = p->next;}
    q->next = t; t->next = p;
   }
  return(head);
}

main()
 { LINKLIST *head, *a1, *a2, *c;
   int num = 0,loop,j;
   char ch;

   loop = 1;
	while (loop) {
	printf("\n\n");
	printf("  1 -- 建立单链表（头插入，不带头结点）\n");
	printf("  2 -- 建立单链表（头插入，带头结点）\n");
	printf("  3 -- 建立单链表（尾插入，不带头结点）\n");
	printf("  4 -- 建立单链表（尾插入，带头结点）\n");
	printf("  5 -- 逆置单链表\n");
	printf("  6 -- 有序链表插入\n");
	printf("  7 -- 有序链表删除重复元素\n");
	printf("  8 -- 无序链表删除重复元素\n");
	printf("  9 -- 两链表合并并排序\n");
	printf(" 10 -- 两链表并集\n\n");
	printf("   请选择项号 ： ");
	scanf("%d",&j);
	fflush(stdin);
	printf("\n\n");
	if(j >= 1 && j <= 10) 
		switch(j) {
			case 1: printf("\n    建立单链表\n\n");
				head = NULL;
				head = creatlink_nohead_head(head);
				fflush(stdin);
				num = count_nohead(head);
				printf("单链表元素个数 = %d\n", num);
				break;
			case 2: printf("\n    建立单链表\n\n");
				head = NULL;
				head = creatlink_head_head(head);
				fflush(stdin);
				num = count_head(head);
				printf("单链表元素个数 = %d\n", num);
				break;
			case 3: printf("\n    建立单链表\n\n");
				head = NULL;
				head = creatlink_nohead_rail(head);
				fflush(stdin);
				num = count_nohead(head);
				printf("单链表元素个数 = %d\n", num);
				break;
			case 4: printf("\n    建立单链表\n\n");
				head = NULL;
				head = creatlink_head_rail(head);
				fflush(stdin);
				num = count_head(head);
				printf("单链表元素个数 = %d\n", num);
				break;
			case 5: printf("\n    建立单链表\n\n");
  				head = NULL;
				head = creatlink_nohead_head(head);
				fflush(stdin);
				num = count_nohead(head);
				printf("单链表元素个数 = %d\n", num);
				printf("\n    逆置单链表\n\n");
				head = invertlink(head);
				num = count_nohead(head);
				break;
			case 6: printf("\n    建立单链表\n\n");
  				head = NULL;
				head = creatlink_order_head(head);
				fflush(stdin);
				num = count_head(head);
				printf("单链表元素个数 = %d\n", num);
				printf("\n输入插入元素值 : ");
				ch = getchar();
				inser_order(ch, head);
				printf("\n    元素插入后\n\n");
				num = count_head(head);
				printf("插入后单链表元素个数 = %d\n", num);
				break;
			case 7: printf("\n    建立单链表\n\n");
  				head = NULL;
				head = creatlink_order_head(head);
				fflush(stdin);
				num = count_head(head);
				printf("\n    删除重复元素后\n\n");
				delete(head);
				num = count_head(head);
				break;
			case 8: printf("\n    建立单链表\n\n");
				head = NULL;
				head = creatlink_head_rail(head);
				fflush(stdin);
				num = count_head(head);
				printf("\n    删除重复元素后\n\n");
				delete1(head);
				num = count_head(head);
				break;
			case 9: printf("\n    建立单链表a1\n\n");
  				a1 = NULL;
				a1 = creatlink_order_head(a1);
				fflush(stdin);
				num = count_head(a1);
				printf("单链表a1元素个数 = %d\n", num);
				printf("\n    建立单链表a2\n\n");
				a2 = NULL;
				a2 = creatlink_order_head(a2);
				fflush(stdin);
				num = count_head(a2);
				printf("单链表a2元素个数 = %d\n", num);
				c = NULL;
				c = (LINKLIST *)malloc(sizeof(LINKLIST));
				c->next = NULL;
				unite(a1, a2, c);
				num = count_head(c);
				printf("合并到单链表c中，元素个数 = %d\n", num);
				break;
			case 10:printf("\n    建立单链表a1 \n\n");
				a1 = NULL;
				a1 = creatlink_head_rail(a1);
				fflush(stdin);
				num = count_head(a1);
				printf("\n    建立单链表a2 \n\n");
				a2 = NULL;
				a2 = creatlink_head_rail(a2);
				fflush(stdin);
				num = count_head(a2);
				printf("\n\n   两链表交集运算,结果保留在a1中\n\n");
				unionn(a1,a2);
				num = count_head(a1); 
		}
	printf("结束此练习吗? (0 -- 结束 1 -- 继续) : ");
	scanf("%d",&loop);
	printf("\n");
	}
}
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -