1、单向链表、双向链表、循环链表

1. #include<stdio.h> 
2. #include<stdlib.h> 
3. #include<malloc.h> 
4. #include<string.h> 
5. struct STU 
6. {
   char name[10]; 
7. char stuno[10]; 
8. int age; 
9. int score; 
10. }; 
11. typedef struct STU ElemType; 
12. struct LNODE 
13. { 
14. ElemType data; 
15. struct LNODE *next; 
16. }; 
17. typedef struct LNODE LNode; 
18. typedef struct LNODE *LinkList; 
19.  
20. int init(LinkList *L) 
21. {*L=(LNode *)malloc(sizeof(LNode)); 
22.   if(!L) 
23.    exit(0); 
24.  memset(&((*L)->data),0,sizeof(struct STU)); 
25.  (*L)->next=NULL; 
26.  return 1; 
27. } 
28.  
29. int ListInsert(LinkList L,int i,ElemType e) 
30. { 
31. LinkList p,s; 
32. int j=0; 
33. p=L; 
34.  
35. while(p&&j<i-1) 
36. {p=p->next; 
37. ++j; 
38. } 
39. if(!p||j>i-1) return 0; 
40.  
41. s=(LinkList)malloc(sizeof(LNode)); 
42. s->data=e; 
43.  
44. s->next=p->next; 
45. p->next=s; 
46. return 1; 
47. } 
48.  
49. int Less_EqualList(ElemType *e1,ElemType *e2) 
50. {
    if(strcmp(e1->name,e2->name)<=0) 
51.    return 1; 
52.   else 
53.    return 0; 
54. } 
55.  
56. void MergeList(LinkList La,LinkList Lb,LinkList *Lc) 
57. { 
58.  LinkList pa,pb,pc; 
59.  pa=La->next; 
60.  pb=Lb->next; 
61.  *Lc=pc=La; 
62.  while(pa&&pb) 
63.  { 
64.   if(Less_EqualList(&pa->data,&pb->data)) 
65.     {pc->next=pa;pc=pa;pa=pa->next;} 
66.   else 
67.     {pc->next=pb;pc=pb;pb=pb->next;} 
68.  } 
69.  pc->next=pa?pa:pb; 
70.  free(Lb); 
71. } 
72.  
73. void printlist(LinkList L) 
74. { 
75. int i; 
76. LinkList p; 
77. p=L; 
78. printf("name      stuno     age     score\n"); 
79. while(p->next) 
80. {p=p->next; 
81. printf("%-10s %s\t%d\t%d\n",p->data.name,p->data.stuno,p->data.age,p->data.score);} 
82. printf("\n"); 
83. } 
84.  
85. //#include<stdio.h> 
86. //#include<malloc.h> 
87. //#include<stdlib.h> 
88. main() 
89. { 
90. struct STU e; 
91. LinkList La,Lb,Lc; 
92. printf("First is InsertList function.\n"); 
93. init(&La); 
94. strcpy(e.name,"stu4"); 
95. strcpy(e.stuno,"100001"); 
96. e.age=80; 
97. e.score=1000; 
98. ListInsert(La,1,e); 
99.  
100. strcpy(e.name,"stu6"); 
101. strcpy(e.stuno,"100002"); 
102. e.age=80; 
103. e.score=1000; 
104. ListInsert(La,2,e); 
105. printlist(La); 
106. getchar(); 
107.  
108. strcpy(e.name,"stu8"); 
109. strcpy(e.stuno,"100003"); 
110. e.age=80; 
111. e.score=1000; 
112. ListInsert(La,3,e); 
113. printlist(La); 
114. getchar(); 
115.  
116. init(&Lb); 
117. strcpy(e.name,"stu5"); 
118. strcpy(e.stuno,"100001"); 
119. e.age=80; 
120. e.score=1000; 
121. ListInsert(Lb,1,e); 
122.  
123. strcpy(e.name,"stu7"); 
124. strcpy(e.stuno,"100002"); 
125. e.age=80; 
126. e.score=1000; 
127. ListInsert(Lb,2,e); 
128.  
129. strcpy(e.name,"stu1"); 
130. strcpy(e.stuno,"100003"); 
131. e.age=80; 
132. e.score=1000; 
133. ListInsert(Lb,3,e); 
134. printlist(Lb); 
135. getchar(); 
136.  
137. MergeList(La,Lb,&Lc); 
138. printlist(Lc); 
139. getchar(); 
140. } 

2、二叉树、平衡树

1. #include <stdio.h> 
2. #include <stdlib.h> 
3. #include <malloc.h> 
4.  
5. struct TNode{ 
6. char data; 
7. struct TNode *lchild; 
8. struct TNode *rchild; 
9. }; 
10. typedef struct TNode Node; 
11.  
12. void init(Node **node) 
13. {  
14.   *node=(Node *)malloc(sizeof(Node)); 
15.   (*node)->lchild=(*node)->rchild=NULL; 
16.   (*node)->data=0; 
17. } 
18.  
19. void construct(char data,Node **node) 
20. { 
21.  int i; 
22.  Node *temp_node=*node; 
23.  while(temp_node) 
24.  { 
25.   if(!temp_node->data) 
26.    {temp_node->data=data; 
27.     break; 
28.     } 
29.  
30.   else if(data<=temp_node->data) 
31.   {
    if(!temp_node->lchild) 
32.    {init(&temp_node->lchild); 
33.     temp_node->lchild->data=data; 
34.     break;} 
35.    else 
36.    {temp_node=temp_node->lchild; 
37.     continue;} 
38.    } 
39.  
40.   else if(data>temp_node->data) 
41.   { 
42.    if(!temp_node->rchild) 
43.    {init(&temp_node->rchild); 
44.     temp_node->rchild->data=data; 
45.     break;} 
46.    else 
47.    {temp_node=temp_node->rchild; 
48.     continue;} 
49.   } 
50.  } 
51.   return; 
52. } 
53.  
54. int PreOrderTraverse(Node *tree_node) 
55. { 
56.    if(tree_node) 
57.    {
    if(printf("%c ",tree_node->data)) 
58.      if(PreOrderTraverse(tree_node->lchild)) 
59.        if(PreOrderTraverse(tree_node->rchild)) 
60.             return 1; 
61.      return 0; 
62.    } 
63.   else 
64.     return 1; 
65. } 
66.  
67. void main() 
68. { 
69.  int i; 
70.  Node *root; 
71.  char data[8]={
    'e','f','h','g','a','c','b','d'}; 
72.  init(&root); 
73.   for(i=0;i<8;i++) 
74.    construct(data[i],&root); 
75.  printf("PreOrder.............\n"); 
76.  PreOrderTraverse(root); 
77. } 

3、哈希表

 实现一个采用开链址法避免冲突的哈希表，哈希函数为key%10，哈希键值如下所示：10，23，34,53,67,865,896,54,46,12,45,2345,43,234

1. #include "stdio.h" 
2. #include "stdlib.h" 
3. #include "string.h" 
4. #include "malloc.h" 
5. #define NUM 10 
6. #define KEYNUM 14 
7. struct elem 
8. {
   int k; 
9.  int si; 
10. }; 
11. typedef struct elem ElemType; 
12.  
13. struct node  
14. {ElemType data; 
15.  struct node *next; 
16. }; 
17. typedef struct node Node; 
18. typedef struct node *List; 
19.  
20. ElemType key[KEYNUM];  
21. List table[NUM]; 
22.  
23. void InitKey() 
24. {
    int i; 
25.   key[0].k=10; 
26.   key[1].k=23; 
27.   key[2].k=34; 
28.   key[3].k=53; 
29.   key[4].k=67; 
30.   key[5].k=865; 
31.   key[6].k=896; 
32.   key[7].k=54; 
33.   key[8].k=46; 
34.   key[9].k=12; 
35.   key[10].k=45; 
36.   key[11].k=2345; 
37.   key[12].k=43; 
38.   key[13].k=234; 
39.  for(i=0;i<KEYNUM;i++) 
40.  {key[i].si=0; 
41.  } 
42.  printf("InitKey() success!!!\n"); 
43. } 
44.  
45. void InitTable(List *L) 
46. { 
47.  *L=(Node *)malloc(sizeof(Node)); 
48.   if(!L) 
49.     exit(0); 
50.  memset(&((*L)->data),0,sizeof(struct elem)); 
51.  (*L)->next=NULL; 
52. } 
53.  
54. void TableInsert(List L,ElemType e) 
55. {List p,s; 
56.  p=L; 
57.  s=(Node *)malloc(sizeof(Node)); 
58.  s->data=e; 
59.  s->next=p->next; 
60.  p->next=s; 
61. } 
62.  
63. void CreateList() 
64. {
    int i,index; 
65.  int num[NUM]; 
66.  ElemType el; 
67.  List p; 
68.  
69.  for(i=0;i<NUM;i++) 
70.   {num[i]=0; 
71.    InitTable(&table[i]); 
72.   } 
73.  for(i=0;i<KEYNUM;i++) 
74.   {index=(key[i].k)%10; 
75.    num[index]++; 
76.    el.k=key[i].k; 
77.    el.si=num[index]; 
78.    index=index-2; 
79.    TableInsert(&table[index],el); 
80.   } 
81. } 
82.  
83. void FindList() 
84. {
    int i,g=0,ch,index; 
85.  List pr; 
86.   printf("Please Enter A Key:\n"); 
87.   scanf("%d",&ch); 
88.   index=ch%10; 
89.   index=index; 
90.   pr=table[index]; 
91.   do 
92.    {
    if(pr->data.k==ch) 
93.      {g=1; 
94.       printf("The address:%d\t The Key:%d \t Search Length:%d \n",index,pr->data.k,pr->data.si);} 
95.      pr=pr->next; 
96.    } 
97.    while(pr); 
98.   if(g==0) printf("no relative key\n"); 
99. } 
100.  
101. void DisplayList() 
102. {
     int i; 
103.  List pr; 
104.   printf("Address \t\t  The Key \t\t Search Length \n"); 
105.   for(i=0;i<NUM;i++) 
106.   { pr=table[i]; 
107.     printf("%d \t ",i); 
108.     do{ 
109.        printf("%d \t  %d \t",pr->data.k,pr->data.si); 
110.        pr=pr->next; 
111.       } 
112.     while(pr); 
113.    printf("\n"); 
114.   } 
115. } 
116.  
117. main() 
118. {
     char ch; 
119.   InitKey(); 
120.   CreateList(); 
121.   do{  
122.      printf("Choose you wanted:D:DisplayList\nF:FindList\nQ:Quit\n"); 
123.      ch=getchar(); 
124.      switch(ch) 
125.       { 
126.        case 'D':DisplayList();break; 
127.        case 'F':FindList();break; 
128.        case 'Q':exit(0); 
129.       } 
130.      printf("come on!y/n?\n"); 
131.      ch=getchar(); 
132.     }while(ch!='n'); 
133. return 0; 
134. }