1、設(shè)有兩個(gè)整型順序表L1，L2，其元素值遞增有序存放，請(qǐng)定義該順序表的元素類型及表類型,設(shè)計(jì)以下自定義函數(shù)：

（1）錄入順序表中所有元素的值。

（2）將順序表L1，L2合并為到另外一個(gè)順序表L3中，L3中的元素非遞減有序排列。

（3）輸出順序表中元素的值。

主函數(shù)通過調(diào)用以上函數(shù)實(shí)現(xiàn)兩個(gè)表的合并并顯示合并結(jié)果。

#include<stdio.h>
#include<stdlib.h>
#define MAXLEN 100 ?? ?
typedef struct
{ ??
? ? int data[MAXLEN+1];
?? ?int len;
}SeqList;?? ??? ?
/*錄入*/
void input(SeqList*L)
{?
? ? int i;
?? ?printf("input the length\n");
?? ?scanf("%d",&L->len);
?? ?printf("input element\n");
?? ?for(i=1;i<=L->len;i++)
?? ? scanf("%d",&L->data[i]);
}
/*合并*/
void merge(SeqList* A , SeqList* B, SeqList *C)
{ ?
?? ?int i,j,k;
?? ?i=1;j=1;k=1; ? ? ? ? ?
?? ?while(i<=A->len&&j<=B->len)
?? ? ? ?if(A->data[i]<B->data[j])
?? ? ? ? ? ?C->data[k++]=A->data[i++];
?? ? ? ?else C->data[k++]=B->data[j++];
?? ?while(i<=A->len)
?? ? ? ? ? ?C->data[k++]=A->data[i++];
?? ? ? ? ? ? while(j<=B->len)
?? ? ? ? ? ? ? ? ? ? ? ? C->data[k++]=B->data[j++];
?? ? ? ? ? ? ?C->len=k-1;?
} ? ? ? ??
/*顯示*/
void output(SeqList*L)
{
? ? int i;
?? ?for(i=1;i<=L->len;i++)
?? ??? ?printf("%5d\n",L->data[i]);
}
/*菜單*/
?? ?void menu()
?? ?{
?? ?printf("1-------------表1錄入\n");
?? ?printf("2-------------表2錄入\n");
?? ?printf("3-------------合并\n");
?? ?printf("4-------------輸出合并后的表\n");
?? ?printf("0-------------退出\n");
?? ?}
int main()
{
?? ?SeqList* L1,*L2,*L3; ?
?? ?int sel;
?? ?L1=(SeqList*)malloc(sizeof(SeqList));
?? ?L1->len=0;?
?? ?L2=(SeqList*)malloc(sizeof(SeqList));
?? ?L2->len=0;?
?? ?L3=(SeqList*)malloc(sizeof(SeqList));
?? ?L3->len=0;?
?? ?do
?? ?{?
?? ? ? menu();
?? ? ? printf("input your select\n");
?? ? ? scanf("%d",&sel);
?? ? ? switch(sel)
?? ? ? {
?? ? ? case 1: ?printf("input list1\n");
?? ? ? ? ? ? input(L1); ? ??
?? ? ? ? ?break;
?? ? ? case 2: printf("input list2\n");
?? ? ? ? ? ?input(L2);
?? ? ? ? ? ?break;
?? ? ? case 3:merge(L1,L2,L3);
?? ? ? ? ? break;
?? ? ? case 4:output(L3);
?? ? ? }
?? ?}while(sel!=0);
?? ?return 0;
}

2、順序表：兩個(gè)表合成一個(gè)新表并排序

#include <stdio.h>
#include <stdlib.h>
#define DataType int ? ? ?//此處假設(shè)順序表的元素基類型為int
#define MAXSIZE 50 ? ? ? ?//此處假設(shè)順序表的最大元素個(gè)數(shù)為50
typedef struct List
{
? DataType data[MAXSIZE]; //用一維數(shù)組存儲(chǔ)順序表元素
? int size; ? ? ? ? ? ? ? ?//線性表的長度?
}SeqList;

void InitList(SeqList *p)//順序表的初始化?
{?
? ? p->size=0;
}?

int ?Locate(SeqList *p, DataType e)
{
? ? int i=0;
? ? while(i<p->size&&p->data[i]!=e)
? ? {
? ? ? ?i++;
? ? }
? ? if(i==p->size)
? ? ? ?return 0;
? ? else
? ? ? ?return(i+1);
}

void InsertList(SeqList *p,int i,DataType e)//插入?
{
? ? int j;
? ? if(i<1||i>p->size+1)
? ? ? ? printf("插入位置不正確");
? ? else
? ? { ??
?? ? ? ?p->size++;
? ? ? ? for(j=p->size-1;j>=i;j--)//此處的size已是修改后的新值
? ? ? ? ? ?p->data[j]=p->data[j-1];
? ? ? ? ? ?p->data[i-1]=e;
? ? }
}
void ?DeleteList(SeqList *p,int i) //其實(shí)刪除的是下標(biāo)i-1的元素
{
? ? ?int j ;
? ? ?if (i<1|| i>p->size)
? ? ?printf( "刪除位置不正確！！");
? ? ? ?else
? ? ?{?
? ? ? ?for(j=i-1;j<p->size-1;j++)
? ? ? ?p->data[j]=p->data[j+1];
? ? ? ?p->size--;
? ? ?}
}
void Display(SeqList *p)//輸出順序表?
{ ?
? ?int j;
? ?if(p->size==0)?
? ? ? ?printf("表為空表！\n");
? ?else
? ? ? for(j=0;j<p->size;j++)
? ? ? ? printf("%d ",p->data[j]);
}
void Bubble(SeqList *p)//升序冒泡?
{
?? ?int i,j;
?? ?int t;
?? ?for(i=0;i<p->size-1;i++)
?? ? ?for(j=i+1;j<p->size;j++)
?? ? ? ? if(p->data[j]<p->data[i])
?? ? ? ?{
?? ??? ?t=p->data[i];
?? ??? ?p->data[i]=p->data[j];
?? ??? ?p->data[j]=t;
?? ? ? ?}?
}
void Bubbles(SeqList *p)//降序冒泡?
{
?? ?int i,j;
?? ?int t;
?? ?for(i=0;i<p->size-1;i++)
?? ? ?for(j=i+1;j<p->size;j++)
?? ? ? ? if(p->data[j]>p->data[i])
?? ? ? ?{
?? ??? ?t=p->data[i];
?? ??? ?p->data[i]=p->data[j];
?? ??? ?p->data[j]=t;
?? ? ? ?}?
}
int main()
?{
?? ?SeqList A={{0,2,4,6,7,9},5},B={{0,1,5,7,8},4},C; ?//第一個(gè)位置不用，然后花括號(hào)外面是表長?
?? ?int i,j;
?? ?InitList(&C);
?? ?for(i=1;i<=A.size;i++)
?? ??? ?InsertList(&C,i,A.data[i]);
?? ?for(j=1;j<=B.size;j++)
?? ??? ?if(Locate(&A,B.data[j])==0)
?? ??? ??? ??? ?InsertList(&C,i++,B.data[j]);
?? ?Display(&C);
?? ?printf("表長=%d\n",C.size);
?? ?printf("\n");
?? ?printf("升序排列：");
? ? Bubble(&C);
?? ?Display(&C);
?? ?printf("\n降序排列：");
? ? Bubbles(&C);
?? ?Display(&C);?? ??? ??? ?
? ? return ?0; ??
}

3、順序表合成：被調(diào)函數(shù)直接返回新表

#include<Stdio.h>
typedef struct A
{?
? ?int data[10];
? ?int len;
}SeqList;
SeqList fun(SeqList *p1, SeqList *p2)
{?
? ? int i,j;
? ? SeqList p;
? ? p.len=p1->len+p2->len;
? ? for(i=0,j=0;i<p1->len;i++)
? ? ? p.data[j++]=p1->data[i];
? ? for(i=0;i<p2->len;i++)
? ? ? p.data[j++]=p2->data[i];
? ? return p; //值帶回，p的空間釋放
}
void main()
{?
? ? int i;
? ? SeqList a={{1,2,3},3},b={{5,6,7,8,9},5},p; //p是一個(gè)實(shí)體對(duì)象，有自己空間
? ? p=fun(&a,&b); //返回值賦值給變量p
? ? for(i=0;i<p.len;i++) // 正確顯示了返回的合并新表的值
? ? ? ?printf("%d ",p.data[i]);
}

4、順序表合成：使用二級(jí)指針,帶回新表

#include <stdio.h>
#include <stdlib.h>
typedef struct
{?
? ?int data[10];
? ?int len;
}SeqList;
void fun(SeqList *p1, SeqList *p2, SeqList **p3)
{?
? ?int i,j;
? ?*p3=(SeqList*)malloc(sizeof(SeqList));
? ?(*p3)->len=p1->len+p2->len;
? ? for(i=0,j=0;i<p1->len;i++)
? ? ? ?(*p3)->data[j++]=p1->data[i];
? ? for(i=0;i<p2->len;i++)
? ? ? (*p3)->data[j++]=p2->data[i];
}?
//二級(jí)指針p3中存放實(shí)參指針的地址，申請(qǐng)的堆空間地地址
//直接寫入實(shí)參指針變量p中，因而返回后訪問堆空間的值是正確的
int main( )
{?
? ?int i;
? ?SeqList a={{1,2,3},3},b={{5,6,7,8,9},5},*p=NULL;
? ?fun(&a,&b,&p); ? ? ? ?//這里使用了指針的指針做實(shí)參
? ?for(i=0;i<p->len;i++) // 正確顯示了返回的合并新表的值
? ?printf("%d ",p->data[i]);
? ?return 0;
}

5、順序表合成：使用靜態(tài)局部變量，返回其內(nèi)存地址給主調(diào)方

#include<stdio.h>
#include<stdlib.h>
typedef struct A
{?
? ?int data[10];
? ?int len;
}SeqList;
SeqList* fun(SeqList *p1,SeqList *p2)
{?
? ?int i,j;
? ?static SeqList p;
? ?p.len=p1->len+p2->len;
? ?for(i=0,j=0;i<p1->len;i++)
? ? ? ?p.data[j++]=p1->data[i];
? ?for(i=0;i<p2->len;i++)
? ? ? ?p.data[j++]=p2->data[i];
? ? return &p; //返回函數(shù)中靜態(tài)局部變量申請(qǐng)的空間地址
}
void main()
{?
? ?int i;
? ?SeqList a={{1,2,3},3},b={{5,6,7,8,9},5},*p;
? ?p=fun(&a,&b); //將返回地址賦值給主調(diào)方的指針變量
? ?for(i=0;i<p->len;i++) // 正確顯示結(jié)果
? ? ? printf("%d ",p->data[i]);
} //靜態(tài)申請(qǐng)的空間釋放

6、順序表合成：被調(diào)函數(shù)返回順序表指針帶回新表地址

#include<stdio.h>
#include<stdlib.h>
typedef struct A
{?
? ?int data[10];
? ?int len;
}SeqList;
?
SeqList* fun(SeqList *p1,SeqList *p2)
{?
? int i,j;
? SeqList *p;
? p=(SeqList*)malloc(sizeof(SeqList));
? p->len=p1->len+p2->len;
? for(i=0,j=0;i<p1->len;i++)
? ? ?p->data[j++]=p1->data[i];
? for(i=0;i<p2->len;i++)
? ? ?p->data[j++]=p2->data[i];
? return p; //帶回指針變量的值，指針變量p的空間釋放
}
int main()
{?
? ?int i;
? ?SeqList a={{1,2,3},3},b={{5,6,7,8,9},5},*p;
? ?p=fun(&a,&b); //返回的地址給了指針變量p
? ?for(i=0;i<p->len;i++) // 正確顯示了返回的合并新表的值
? ? ? printf("%d ",p->data[i]);
? ?return 0;
}

7、堆排序

#include<stdio.h>
#define MAXSIZE 100?
typedef struct
{
?? ?int key;
}DataType;
typedef struct
{
?? ?DataType list[MAXSIZE];
?? ?int length;
}SeqList;
void HeapAdjust(SeqList *L,int low,int high)?
{?
? ? int i, j;
? ? i=low;?
? ? j=2*i;?
? ? L->list[0]=L->list[i];?
? ? for(;j<=high;j*=2)?
? ? {?
?? ? if(j<high&&L->list[j].key<L->list[j+1].key)
? ? ? ?j++;
? ? ?if(L->list[0].key>=L->list[j].key)?
? ? ? ?break;?
? ? ?else?
? ? ?{?
?? ? ? L->list[i]=L->list[j];
? ? ? ?i=j;?
? ? ?}
? ? }
? ? L->list[i]=L->list[0];?
}
void HeapCreate(SeqList *L)?
{?
? ?int i, n;
? ?n=L->length;
? ?for(i=n/2;i>0;i--)
? ?HeapAdjust(L,i,n);
}
void HeapSort(SeqList *L)
{?
? ? int i, n=L->length;
? ? HeapCreate(L);
? ? for(i=n;i>1;i--)
? ? {?
?? ? ?L->list[0]=L->list[1];
? ? ? L->list[1]=L->list[i];?
? ? ? L->list[i]= L->list[0];
? ? ? HeapAdjust(L,1,i-1);
? ? }
}
int main()
{
? ? SeqList L={{0,18,27,10,8,18,38,4,17,21},10};
? ? HeapCreate(&L);
?? ?HeapSort(&L);
?? ?int i;
?? ?for(i=1;i<=10;i++)
?? ?{
?? ??? ?printf("%d ",L.list[i].key);
?? ?}?
?? ?return 0;?? ?
}?

8、快速排序

#include<stdio.h>
#define MAXSIZE 100
typedef struct
{
?? ?int key;
}DataType;
typedef struct
{
?? ?DataType list[MAXSIZE];
?? ?int length;
}SeqList;
int QuickPass(SeqList *L,int low,int high)?
{?
? ?int i,j;
? ?i=low;
? ?j=high;?
? ?L->list[0]=L->list[i];
? ?while(i!=j)
? ?{?
? ? ?while((L->list[j].key>=L->list[0].key)&&(i<j))?
?? ? j--;
? ? ?if(i<j)
? ? {?
?? ? ? L->list[i]=L->list[j];?
?? ? ? i++;?
?? ?}
? ? while((L->list[i].key<=L->list[0].key)&&(i<j))?
?? ? ?i++;
? ? if(i<j)?
? ? {?
?? ? ?L->list[j]=L->list[i];?
?? ? ?j--;?
?? ?}
? ?}
? ?L->list[i]=L->list[0];?
? ?return i;
}
void QuickSort(SeqList *L,int s,int t)?
{?
? ?int i;
? ?if(s<t)
? ?{
? ? i=QuickPass(L,s,t);
? ? QuickSort(L,s,i-1);
? ? QuickSort(L,i+1,t);
? ?}
}
int main()
{
? ? //SeqList L={{0,38,20,46,38,74,91,25,12},9};
? ? SeqList L={{0,18,27,10,8,19,38,4,17,21},10};
?? ?QuickSort(&L,1,10);
?? ?int i;
?? ?for(i=1;i<=10;i++)
?? ?{
?? ??? ?printf("%d ",L.list[i].key);
?? ?}
?? ?return 0;?? ?
}?

9、直接插入排序

void ?ins_sort(int R[ ],int *n，int x)
{ ?
? ? int i;
?? ?R[0]=x; ? ? ? ?
?? ?i=*n; ? ? ? ? ? ? ??
?? ?while( R[0]<R[i])
?? ?{?
?? ? ? ?R[i+1]=R[i]; ? ? ? ??
?? ? ? ?i--;
?? ?} ? ? ? ? ? ? ? ??
?? ?R[i+1]=R[0]; ??
?? ?(*n)++;
}

10.寫出用直接插入排序進(jìn)行升序排序的算法

void ?ins_sort（datatype R[ ],int n）
?? ?{ ?int i;
?? ? ? ?for( i=2;i<=n;i++)
?? ? ? ? ?{ R[0]=R[i]; ? ? ? ?
?? ? ? ? ? j=i-1; ? ? ? ? ? ? ??
?? ? ? ? ? while( R[0].key<R[j].key )
?? ? ? ? ? ? { R[j+1]=R[j] ; ? ? ? ??
?? ? ? ? ? ? ? ?j- -;
?? ?} ? ? ? ? ? ? ? ??
?? ? ? ? ? R[j+1]=R[0] ; ??
?? ? ? ? ? }
?? ? ?}

10、//給定一組整型值，-1作為結(jié)束，寫出二叉排序樹的生成過程。
?? ?void insert(BiTree t, Bstree * s) ? //將s插入到t為根的二叉排序樹中
?? ?{ ?
?? ?if(s->data<t->data)
?? ?{ ?
?? ?if (t->lchild==NULL)
?? ? ? ?t->lchild=s;
?? ? ? ?else ? ??
?? ??? ?insert(t->lchild,s);
?? ?}
?? ?else
?? ?{ ?
?? ?if (t->rchild==NULL)
?? ? ? ?t->rchild=s;
?? ? ? ?else
?? ? ? ? ? ?insert(t->rchild,s);
?? ? ? ?}
?? ?}
?? ?Bstree* bstreecreate() /*二叉排序樹的生成算法*/
?? ?{ ?
?? ? ? int x;
?? ? ? Bstree *s,*t;
?? ? ? t=NULL;
?? ? ? printf("input the elements of bstree,end flag is -1\n");
?? ? ? scanf("%d",&x);
?? ? ? while(x!=-1) ? ??
?? ? ? { ?
?? ? ? s=(BiTNode*)malloc(sizeof(BiTNode));
?? ? ? ? ? ?s->data=x;
?? ? ? ? ? ?s->lchild=s->rchild=NULL;
?? ? ? ? ? ?if (t==NULL)
?? ? ? ? ? ? ? t=s;
?? ? ? ? ? ?else
?? ? ? ? ? ? ? ?insert(t,s);
?? ? ? ? ? ?scanf("%d",&x);
?? ? ? ? }
?? ? ?return (t);
?? ?}

11、哈希查找#include <stdio.h>
#include <stdlib.h>
#define NULLKEY 0
#define DELKEY -1
typedef struct?
{
? ? int key;
}Haxi;
int Hash(int k)
{?
? ? int i;
? ? i=k%97;
? ? return i;
}
int InsertHash(Haxi ht[],int m,int k)
{
?? ?int h0,hi,di;
?? ?h0=Hash(k);
?? ?hi=h0;
?? ?di=1;
?? ?while(ht[hi].key!=NULLKEY&&ht[hi].key!=DELKEY&&ht[hi].key!=k&&di<m)
?? ?{
?? ??? ?hi=(h0+di)%m;
?? ??? ?di++;
?? ?}
?? ?if(ht[hi].key!=k&&di<m)
?? ?{
?? ??? ?ht[hi].key=k;
?? ??? ?return 1;
?? ?}
?? ?else
?? ?{
?? ??? ?if(ht[hi].key==k)
?? ??? ? ?printf("元素%d已經(jīng)存在\n",k);
?? ??? ?else
?? ??? ?printf("哈希表已滿\n");
?? ??? ?return 0; ?
?? ?}
}
void CreateHash(Haxi ht[],int m)
{
?? ?int endflag=-99999;
?? ?int i,x;
?? ?for(i=0;i<m;i++)
?? ?{
?? ??? ?ht[i].key=NULLKEY;
?? ?}
?? ?printf("請(qǐng)輸入哈希表中各個(gè)元素的值，以endflag=-99999結(jié)束：\n");
?? ?scanf("%d",&x);
?? ?while(x!=endflag)
?? ?{
?? ??? ?InsertHash(ht,m,x);
?? ??? ?scanf("%d",&x);
?? ?}
}
int SearchHash(Haxi ht[],int m,int k)
{
?? ?int h0,hi,di;
?? ?h0=Hash(k);
?? ?hi=h0;
?? ?di=1;
?? ?while(ht[hi].key!=NULLKEY&&ht[hi].key!=k&&di<m)
?? ?{
?? ??? ?hi=(h0+di)%m;
?? ??? ?di++;
?? ?}
? ? if(ht[hi].key==k)
?? ??? ?return hi;
?? ?else
? ? ? ? return -1;
}
int DeleteHash(Haxi ht[],int m,int k)
{
?? ?int i;
?? ?i=SearchHash(ht,m,k);
?? ?if(i!=-1)
?? ?{
?? ??? ?ht[i].key=DELKEY;
?? ??? ?return 1;
?? ?}
?? ?else
?? ?return 0;
}
int main()
{
//測(cè)試數(shù)據(jù):62 30 18 45 21 78 66 32 54 48 -99999
?? ?Haxi ht[100];
?? ?int i,j;
?? ?int huanhang=0;
?? ?CreateHash(ht,100);
?? ?int number;
?? ?int q;
?? ?do
?? ?{
?? ??? ?printf("請(qǐng)輸入你想進(jìn)行的操作:\n1.查看哈希表\n2.查找哈希表中的元素\n3.刪除哈希表中的元素\n0.退出\n");
?? ??? ?scanf("%d",&q);
?? ??? ?switch(q)
?? ??? ?{
?? ??? ??? ?case 1:?? ?printf("下面是建立的哈希表：\n\n");
?? ? ? ? ? ? ? ? ? ?for(i=0;i<=99;i++)
?? ? ? ? ? ? ? ? ? ?{
?? ??? ? ? ? ? ? ? ?printf("%d ? ?",ht[i].key);
?? ? ? ? ? ? ? ? ? ?huanhang++;
?? ? ? ? ? ? ? ? ?? ?if(huanhang%10==0)
?? ? ? ? ? ? ? ? ? ?? ? ?{
?? ??? ? ? ? ? ? ? ?? ? ? ?printf("\n");
?? ? ? ? ? ? ? ? ? ? ?}
?? ? ? ? ? ? ? ? ? ?}
?? ? ? ? ? ? ? ? ? ?break;
?? ? ? ? ? ?case 2: printf("請(qǐng)輸入你想查找的元素:\n");
?? ? ? ? ? ? ? ? ? ?scanf("%d",&number);
?? ? ? ? ? ? ? ? ? ?j=SearchHash(ht,100,number);
?? ? ? ? ? ? ? ? ? ?if(j==-1)
?? ? ? ? ? ? ? ? ? ?{
?? ? ? ? ? ? ? ? ? ??? ?printf("查找失敗，該元素不存在!\n\n");
?? ??? ??? ??? ??? ?}else
? ? ? ? ? ? ? ? ? ? printf("元素%d在第%d個(gè)位置上",number,j); ?
? ? ? ? ? ? ? ? ? ? break;
?? ??? ??? ?case 3: printf("請(qǐng)輸入你想刪除的元素:");
? ? ? ? ? ? ? ? ? ? int delnumber;
? ? ? ? ? ? ? ? ? ? int sign;
? ? ? ? ? ? ? ? ? ? scanf("%d",&delnumber);
? ? ? ? ? ? ? ? ? ? sign=DeleteHash(ht,100,delnumber);
? ? ? ? ? ? ? ? ? ? if(sign==1)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ?? ?printf("刪除成功，該元素所在位置置為0\n");
?? ??? ??? ??? ??? ?}else
?? ??? ??? ??? ??? ?printf("查找失敗！該元素不存在\n");
? ? ? ? ? ? ? ? ? ? break;
?? ??? ?}
?? ?}while(q);
?? ?return 0;
}

11、v單鏈表操作

#include ?<stdio.h>
#include <stdlib.h>
#define N 0
typedef struct
{
?? ?int sno;
?? ?char name[20];?? ?
}DataType;
typedef ?struct ? Node
{ ? DataType ?data;
? ? struct Node *next;
}LNode,*LinkList;
LNode * InitL( )//初始化從無到有
{ ?LNode ?*head=NULL;
? ? head=(LNode*)malloc(sizeof(LNode));
? ? if(head!=NULL)?
? ? ? ? ? ? ? head->next=NULL;?
? ? ?return ?head;
}
LNode* CreatLinkH (LNode ?*head, int n)
{ ? LNode ?*s;
? ? DataType ? x;
?? ?int k=0;
? ? while(k<n)
? ? { ? scanf("%d%s",&x.sno,x.name);
?? ??? ?s=(LNode*)malloc(sizeof(LNode)); ?/*為新結(jié)點(diǎn)s申請(qǐng)空間*/
? ? ? ? s->data=x; ? ? ? ? ? ? ? ? /*給新結(jié)點(diǎn)的數(shù)據(jù)域賦值*/ ? ? ? ? ? ? ? ? ? ??
? ? ? ?s->next=head->next;/*將新結(jié)點(diǎn)鏈到首元結(jié)點(diǎn)之前*/
? ? ? ?head->next=s; ? ? ? ? ?/*將新結(jié)點(diǎn)鏈到頭結(jié)點(diǎn)之后*/?
? ? ? ?k++;
? ? ?}
?? ?return head;
}
void display(LNode ?*head)//顯示帶頭結(jié)點(diǎn)的單鏈表的所有信息
{?? ?LNode ?*p;
?? ?p=head->next;//P指向了第一個(gè)數(shù)據(jù)結(jié)點(diǎn)
?? ?while(p!=NULL)//說明 p指向了一個(gè)實(shí)際的數(shù)據(jù)結(jié)點(diǎn)
?? ?{?? ?printf("%5d%10s\n",p->data.sno,p->data.name);//輸出該結(jié)點(diǎn)的值
?? ??? ?p=p->next;//p下移到下一個(gè)結(jié)點(diǎn)
?? ?}
?? ?printf("\n");
}
/*
LNode * SearchL(LNode *head, ?DataType ?x)//返回找到結(jié)點(diǎn)的地址
{ ? LNode ?*p;
?
? ? p=head->next; ? ? ? ? ? ? ? ? ? ? ?//從第一個(gè)結(jié)點(diǎn)開始找
? ? ?while(p!=NULL && p->data!=x ) ? ? //逐個(gè)往后查找
?? ? { ? ? ?p=p->next;}
? ? ? return ? p;
}
*/
LNode * Search_i(LNode *head, int i)//返回第i個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)
{ ? LNode ?*p;
?? ?int k=0;
? ? p=head; ? ? ? ? ? ? ? ? ? ? ?//從第一個(gè)結(jié)點(diǎn)開始找
? ? ?while(p && k<i-1 ) ? ? //逐個(gè)往后查找
?? ? { ? k++; ? p=p->next;
?? ? }
?? ?if(p==NULL||i<1)
?? ??? ?return NULL;
?? ?return ? p;
}
void Insert_i(LNode *head, int i)
{
?? ?LNode *p,*s;
?? ?p=Search_i(head, i);
?? ?if(p)
?? ?{?? ?s=(LNode*)malloc(sizeof(LNode)); ?/*為新結(jié)點(diǎn)s申請(qǐng)空間*/
?? ??? ?scanf("%d%s",&s->data.sno,s->data.name);
?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? s->next=p->next;
? ? ? ? p->next=s; ?
?? ?}
}
void DeleteL_i(LNode *head, int i)
{
?? ?LNode *p,*s;
?? ?p=Search_i(head, i);
?? ?if(p==NULL)
?? ??? ?printf("查無此值！\n");
?? ?else
?? ? ?if(p->next!=NULL)
?? ? ?{?? ?
?? ??? ?s=p->next;
?? ??? ?p->next=s->next;
?? ??? ?free(s);
?? ??? ?}?? ? ? ?
}
LNode * SearchL_2(LNode *head, ?DataType ?x)//返回找到結(jié)點(diǎn)的位置號(hào)
{ ? LNode ?*p;
? ? p=head->next; ? ? ? ? ? ? ? ? ? ? ?//從第一個(gè)結(jié)點(diǎn)開始找
? ? ?while(p!=NULL && p->data.sno!=x.sno ) ? ? //逐個(gè)往后查找
?? ? { ? p=p->next;}
? ? return ?p;?? ??
}
int ?count_len(LNode *head)//返回找到結(jié)點(diǎn)的位置號(hào)
{ ? LNode ?*p;
?? ?int n=0;
? ? ?p=head->next; ? ? ? ? ? ? ? ? ? ? ?//從第一個(gè)結(jié)點(diǎn)開始找
? ? ?while(p!=NULL ?) ? ? //逐個(gè)往后查找
?? ? { ++n; ?p=p->next;}
? ? return ?n;?? ??
}
int main()
{?? ?LNode ?*head=NULL,*p;
?? ?DataType ?x;
?? ?int i;
?? ?head=InitL();
?? ?head=CreatLinkH(head,N);//頭插法建立鏈表
?? ?display(head);
//?? ?scanf("%d",&x.sno);
//?? ?p=Search_i(head, i);

/*?? ?if(p==NULL)
?? ??? ?printf("查無此值！\n");
?? ?else
?? ??? ?if(p==head)
?? ??? ??? ?printf("是頭結(jié)點(diǎn)\n");
?? ??? ?else
?? ??? ??? ?printf("%5d%10s\n",p->data.sno,p->data.name);
?? ?Insert_i(head,i);
?? ?display(head);

?? ?DeleteL_i(head,i);
?? ?display(head);
?? ?p=SearchL_2(head, x);
?? ?if(p)
?? ??? ?printf("%5d%10s\n",p->data.sno,p->data.name);
?? ?else
?? ??? ?printf("查無此值！\n");
?? ?*/
?? ?printf("長度：%d\n",count_len(head));
?? ?return 0;
}

12雙向鏈表

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{?
?? ?int sno;
?? ?char sex[3];
?? ?char name[20];
}DataType;?
typedef struct DNode
{
?? ?DataType data;
? ? struct DNode *prior,*next;
}DNode,*DuLinklist;
void CrtlinkR(DNode **head,int n)/*創(chuàng)建長度為n的雙向鏈表*/
{
?? ?int i;
?? ?DNode *p,*rear;
?? ?*head=(DNode *)malloc(sizeof(DNode));
?? ?rear=*head;
?? ?(*head)->prior=NULL;
?? ?printf("input data:\n");
?? ?for(i=1;i<=n;i++)
?? ?{
?? ??? ?p=(DNode*)malloc(sizeof(DNode));
?? ??? ?scanf("%d%s%s",&p->data.sno,p->data.sex,p->data.name);
?? ??? ?rear->next=p;
?? ??? ?p->prior=rear;
?? ??? ?rear=p;
?? ?}
?? ?rear->next=NULL;
}
void serch_i_2(DNode *head,int i)
{
?? ?DNode *p,*s,*t;
?? ?int k=0;
?? ?p=head;
?? ?while(p&&k<i)
?? ?{
?? ??? ?k++;p=p->next;
?? ?}
?? ?if(i<3||p==NULL||p->prior==NULL||p->prior->prior==NULL)
?? ??? ?printf("向前無第2個(gè)結(jié)點(diǎn)\n");
?? ?else
?? ?{
?? ??? ?s=p->prior->prior;
?? ??? ?printf("%5d %5s %10s\n",s->data.sno,s->data.sex,s->data.name);
?? ?}
?? ?if(p==NULL||p->next==NULL||p->next->next==NULL)
?? ??? ?printf("向后無第2個(gè)結(jié)點(diǎn)\n");
?? ?else
?? ?{
?? ??? ?t=p->next->next;
?? ??? ?printf("%5d %5s %10s\n",t->data.sno,t->data.sex,t->data.name);
?? ?}
}
void dispheady(DNode *head)
{
?? ?DNode *p;
?? ?p=head;
?? ?while(p->next!=NULL)
?? ?{
?? ??? ? printf("%5d %5s %10s\n",p->next->data.sno,p->next->data.sex,p->next->data.name);
?? ??? ? p=p->next;
?? ?}
?? ?printf("\n");
?? ?
}
/*
int dLinkdel(DuLinklist L,int i)
{
?? ?DNode *p,*s;
?? ?int j;
?? ?p=L;
?? ?j=0;
?? ?while(p!=NULL&&j<i)
?? ?{
?? ??? ?p=p->next;
?? ??? ?j++;
?? ?
?? ?}
?? ?if(j!=i||i<1)
?? ?{
?? ??? ?printf("刪除位置不正確\n");
?? ??? ?return 0;
?? ?}
?? ?s=p ; ?
?? ?
? ? printf("p->data=%d\n",p->data);
?? ?
?? ?p->prior->next=p->next;
?? ?if(p->next!=NULL)
?? ?p->next->prior=p->prior;
?? ?
?? ?free(s);

?? ?return 1;
}
*/
? void fun(DNode *head,DNode **M,DNode **F)
? {
?? ??? ?DNode *p,*rf,*rm,*s;
?? ??? ?CrtlinkR(M,0);
?? ??? ?CrtlinkR(F,0);
?? ??? ?rf=*F;
?? ??? ?rm=*M;
?? ??? ?p=head->next;
?? ??? ?while(p)
?? ??? ?{
?? ??? ??? ?if(strcmp(p->data.sex,"男")==0)
?? ??? ??? ?{
?? ??? ??? ??? ?s=(DNode *)malloc(sizeof(DNode));
?? ??? ??? ??? ?s->data=p->data;
?? ??? ??? ??? ?s->prior=rf;
?? ??? ??? ??? ?s->next=rf->next;
?? ??? ??? ??? ?rf->next=s;
?? ??? ??? ??? ?rf=s;?? ?
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?s=(DNode *)malloc(sizeof(DNode));
?? ??? ??? ??? ?s->data=p->data;
?? ??? ??? ??? ?s->prior=rm;
?? ??? ??? ??? ?s->next=rm->next;
?? ??? ??? ??? ?rm->next=s;
?? ??? ??? ??? ?rm=s;
?? ??? ??? ?}
?? ??? ??? ?p=p->next;
?? ??? ?}
? }
void fun_2(DNode *head,DNode **M,DNode **F)//拆男生和女生
? {
?? ??? ?DNode *p,*rf,*rm,*s;
?? ??? ?CrtlinkR(M,0);
?? ??? ?*F=head;
?? ??? ?rf=*F;
?? ??? ?rm=*M;
?? ??? ?p=head->next;
?? ??? ?while(p)
?? ??? ?{
?? ??? ??? ?if(strcmp(p->data.sex,"男")==0)
?? ??? ??? ?{
?? ??? ??? ??? ?s=p;
?? ??? ??? ??? ?p=p->next;
?? ??? ??? ??? ?s->next=rf->next;
?? ??? ??? ??? ?rf->next=s;
?? ??? ??? ??? ?rf=s;?? ??? ?
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?s=p;
?? ??? ??? ??? ?p=p->next;
?? ??? ??? ??? ?s->next=rm->next;
?? ??? ??? ??? ?rm->next=s;
?? ??? ??? ??? ?rm=s;
?? ??? ??? ?}?? ??? ??? ?
?? ?}
?? ??? ?rf->next=NULL;
?? ??? ?rm->next=NULL;
? }
int ?main()
{
?? ?DNode *head,*Mhead,*Fhead;
?? ?int i,k;
?? ?CrtlinkR(&head,5); ?/*新建一個(gè)長度為5的雙向鏈表*/
?? ?dispheady(head); ? ?/*顯示雙向鏈表*/
?? ?/*
?? ?i=locate(head,2); ?//查找數(shù)據(jù)4所在位置
?? ?printf("%d\n",i);
?? ?k=dLinkdel(head,i);//刪除第i個(gè)數(shù)據(jù)
? ??
?? ?if(k==1) ? ?//刪除成功則顯示插入后雙向鏈表
?? ?{
?? ??? ?printf("已正確刪除了第%d個(gè)結(jié)點(diǎn)\n",i);
?? ??? ?dispheady(&head);
?? ?}
?? ?else
?? ??? ?printf("位置不正確，不能刪除\n");
?? ?scanf("%d",&i);
?? ?serch_i_2(head,i);*/
?? ??? ?fun_2(head,&Mhead,&Fhead);
?? ??? ?dispheady(Mhead);
?? ??? ?dispheady(Fhead);
?? ??? ?dispheady(head);
?? ?return 0;
}

13樹

//1. 設(shè)計(jì)一算法，統(tǒng)計(jì)二叉樹中度為2的結(jié)點(diǎn)總數(shù)。
int count(Bstree* bt)
{ ?
?? ?if(bt==NULL)?
?? ?return 0; ? ? ? ??
?? ?if(bt->lchild!=NULL&&bt->rchild!=NULL)?
?? ? ? ?return 1; ? ? ? ??
?? ?else
?? ? ? ?return(count(bt->lchild)+count(bt->rchild)); ?
}

//3. 設(shè)計(jì)一算法，統(tǒng)計(jì)葉子結(jié)點(diǎn)總數(shù)。
int countleaf1(Bstree* bt)
{ ?
?? ?if(bt==NULL)?
?? ??? ?return 0; ? ? ? ??
?? ?if(bt->lchild==NULL && bt->rchild==NULL)?
?? ? ? ?return 1; ? ? ? ?
?? ?else
?? ? ? ?return(countleaf1(bt->lchild)+countleaf1(bt->rchild)); ? ?
}

//寫出在二叉排序樹中進(jìn)行查找的算法。
BiTNode* SearchData(BiTree t, KeyType kx)
/*在二叉排序樹t上查找關(guān)鍵碼為kx的元素,找到返回其所在及結(jié)點(diǎn)的指針，否則返回一個(gè)空指針 */
{
? ? BiTNode* q=t;
?? ? ? ?while(q)
?? ? ? ?{
?? ??? ?if(kx>q->data.key)
?? ? ? ? ? ?q=q->rchild; ?/* 在右子樹中查找 */?
? ? ? ? ? ? else if (kx<q->data.key)?
?? ? ? ? ? ? ? ? ? ?q=q->lchild; /* 在左子樹中查找 */?
?? ? ? ? ? ? ? ?else return q; ? /* 查找成功 */
?? ? ? ?} ??
?? ?return ?NULL; ? ?/* 查找不成功 */
}

中序遍歷

typedef struct node
{
?? ?int ?data;
?? ?struct node *lchild,*rchild;
}Bstree;
?? ?
void bianli(Bstree* bt)
{ ?
?? ?if (bt!=NULL)
?? ?{ ?
?? ??? ?bianli(bt->rchild);
?? ? ? ?printf("%5d,",bt->data);?
?? ? ? ?bianli(bt->lchild);
?? ?} ? ? ?
}

二叉樹判斷完全二叉樹源代碼typedef struct?
{
?? ?char data[10];
?? ?int front;
?? ?int rear;
}SeqQueue;
/*
void initqueue(SeqQueue *q)
{
?? ?q->front=q->rear=0;
}
int enqueue(SeqQueue *q,char x)
{
?? ?if(q->rear==10)
?? ?{
?? ? ? printf("隊(duì)滿\n");
? ? }
? ? else
? ? {
? ? ?? ?q->data[q->rear]=x;
? ? ?? ?q->rear++;
? ? ?? ?return 1;
?? ?}
?? ?return 0;
}
int dequeue(SeqQueue *q,char *x)
{
?? ?if(q->front==q->rear)
?? ?{
?? ??? ?printf("隊(duì)空");
?? ??? ?return 0;
?? ?}
?? ?else
?? ?{
?? ??? ?*x=q->data[q->front];
?? ??? ?q->front++;
?? ??? ?return 1;
?? ?}
?? ?
}
/*
void complete(BiTree root)
{
?? ?SeqQueue p;
?? ?BiTree q=root;
?? ?initqueue(&p);
?? ?if(q!=NULL)
?? ?{
?? ??? ?enqueue(&amp;p,*q);
?? ??? ?while(p.front&lt;p.rear)
?? ??? ?{
?? ??? ??? ?dequeue(&amp;p,q);
?? ??? ??? ?printf("%c",q);
?? ??? ??? ?if(q->lchild!=NULL)
?? ??? ??? ?enqueue(&amp;p,*(q->lchild));
?? ??? ??? ?if(q->rchild!=NULL)
?? ??? ??? ?enqueue(&amp;p,*(q->rchild));
?? ??? ?}
?? ?}
}
*/
/*?
bool Judge_Complete(BiTree T)//判斷二叉樹是否是完全二叉樹
{
BiTree t;
SeqQueue Q; ? ? //創(chuàng)建一個(gè)空隊(duì)列
initqueue(&Q);
enqueue(&Q,T); //將T的頭結(jié)點(diǎn)入隊(duì)
t = T; ? ? ? ? //給t賦初值T根節(jié)點(diǎn)
if(T==NULL)
return false;
while(QueueLength(Q))
{
if(t->lchild==NULL && t->rchild!=NULL)
return false;
if(t->lchild!=NULL && t->rchild!=NULL)//左右孩子都不為空
{
dequeue(&Q,t);//刪除該雙親節(jié)點(diǎn)
enqueue(&Q,t->lchild); //將左孩子入隊(duì)
enqueue(&Q,t->rchild); //將右孩子入隊(duì)
}
if((t->lchild!=NULL && t->rchild==NULL) || (t->lchild==NULL && t->rchild==NULL))
{
dequeue(&Q,t); //從剛才判斷的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)一次判斷剩下隊(duì)列中的節(jié)點(diǎn)是否左右子樹都為空
while(QueueLength(Q))
{
if(t->lchild==NULL && t->rchild==NULL)
dequeue(&Q,t);
else
return false;
}
return true;
}
}
return true;
}
*/
在順序表中進(jìn)行二分查找的遞歸算法int BSearch(S_TBL *tbl,keytype kx，int low,int high)
//在下界為low，上界為high的線性表tbl中折半查找關(guān)鍵字為k的元素
{ ? int ?mid=(low+high)/2;
?? ?if(low>high) return -1; ? ?
?? ?if(k==tbl->data[mid].key) return mid;
?? ?if(k< tbl->data[mid].key) return(BSearch(tbl,k,low,mid-1));
?? ?return(BSearch(tbl,k,mid+1,high));
}

折半查找

#include<stdio.h>
#define MAXSIZE 100
#define KeyType int
typedef struct STUDENTS
{
?? ?char name[10];?
?? ?int grade; ? ?
}stu;

typedef struct ?
{
??? ?stu data[MAXSIZE+1];
??? ?int length;
}SeqList;

int Binsearch(SeqList *L,KeyType x)
{?
? ? int low,mid,high;
? ? low=1;?
?? ?high=L->length;
? ? while(low<=high)
? ? {?
?? ? ?mid=(low+high)/2;
? ? ? if(L->data[mid].grade==x)
? ? ? return mid;
? ? ? else
? ? ? ? ? if(L->data[mid].grade<x)
? ? ? ? ? low=mid+1;
? ? ? ? ? else
? ? ? ? ? high=mid-1;
? ? }
? ? return 0;
}
int main()
{
?? ?SeqList m={
?? ? ? ? ? ? ? {
?? ? ? ? ? ? ? {"",0},
?? ??? ??? ? ? {"張三",60},
?? ? ? ? ? ? ? {"李四",70},
?? ??? ??? ? ? {"王五",80},
?? ??? ??? ? ? {"老六",90}},
?? ??? ??? ? ? ?4};
?? ?int searchgrade;
?? ?int location;
?? ?printf("請(qǐng)輸入你想要查找的成績:\n");
?? ?scanf("%d",&searchgrade);
?? ?location=Binsearch(&m,searchgrade);
?? ?if(location!=0)
?? ?{
?? ?printf("%s",m.data[location].name);
? ? }
?? ?else{
?? ?printf("查無此人");?? ?
? ? }
?? ?return 0;?? ??? ??
}

有兩個(gè)鏈表表示的集合，設(shè)計(jì)算法判斷是否相等源代碼

// 判斷兩個(gè)鏈表表示的集合是否相等
int Equal(LinkList h1,LinkList h2)
{ LNode *p,*q;
?int t1=0,t2=0;?
?p=h1->next; q=h2->next;?
?while(p) //h1中所有元素是否都在h2
?{ if(locateLinkList(h2,p->data))
p=p->next;
?else return 0;
?}
?if(p==NULL) t1=1;
?while(q) //h2中所有元素是否都在h1
?{ if(locateLinkList(h1,q->data))
?q=q->next;
?else return 0 ;
?}
?if(q==NULL)
t2=1;
?if(t1==1&&t2==1) return 1 ;
?else return 0;
}

//
// 判斷兩個(gè)有序鏈表表示的集合是否相等
int Equal(LinkList h1,LinkList h2)
{ LNode *p,*q;
?p=h1->next;q=h2->next;
?while(p&&q) //等長且對(duì)應(yīng)元素一一相等
?{ if(p->data!=q->data)
?return 0;
?p=p->next;q=q->next;
?}
?if(p||q)
return 0;
?return 1;
}?

//設(shè)計(jì)一算法利用單鏈表中原來的結(jié)點(diǎn)將該單鏈表中元素倒置。即：原來的元素如果為：1，2，3，4，5；倒置后變成5，4，3，2，1。?
void reverse (NodeType * H)
{ ?
? ? NodeType *p;?
?? ?p=H-> next;
?? ?H->next=NULL;
?? ?while(p)
?? ?{ ??
?? ?q=p;?
?? ?p=p->next;
?? ?q->next=H->next;
?? ?H->next=q; ??
?? ?}
}

10. 設(shè)計(jì)一算法，求該鏈表中值最大的結(jié)點(diǎn)并返回該結(jié)點(diǎn)的指針，若鏈表為空，則返回一個(gè)
空指針。
?? ?NodeType* maxpNodeType* L)
?? ?{ ?NodeType* p=L->next,*s;
?? ? ? if(p!=NULL)
?? ?{ ? s=p; ?//第一個(gè)結(jié)點(diǎn)初始化為最大的結(jié)點(diǎn)
?? ? ? ? ? ?p=p->next; ?//從第二個(gè)開始比較
?? ? ? ? ? ?while(p!=NULL)
?? ? ? ? ? ?{ ? if(p->data>s->data) ?s=p; ?//s指向當(dāng)前最大的結(jié)點(diǎn)
?? ? ? ? ? ? ? ?p=p->next;
?? ?}
?? ?return s；
?? ? ?｝
?? ?else
?? ? ? return ?NULL；
?? ?}

3. 設(shè)計(jì)一算法刪除單鏈表中重復(fù)的結(jié)點(diǎn)。
?? ?void pur_LinkList(NodeType * H)
?? ?{ NodeType *p,*q,*r; ? ? ? ? ? ? ? ? ? ? ?
?? ? ? p=H->next;
?? ? ? ? ?if (p==NULL) return；
?? ? ? ? ?while(p->next)
?? ? ? ? ?{ ?q=p; //找與p重復(fù)的結(jié)點(diǎn)并刪除
?? ? ? ? ? ? while(q->next)
?? ? ? ? ? ? ? if (q->next->data==p->data)
?? ? ? ? ? ? ? ? ? ? ?{ r=q->next; ?q->next=r->next; free( r ); }
?? ? ? ? ? ? ? else q= q ->next;
?? ? ? ? ? ? p=p->next;
?? ? ? ? ? ?}
?? ??