数据结构实验报告姓名:wangqiang学号：*********1线性表的应用#include<stdio.h>#include<stdlib.h>typedef struct node{int value;struct node *next;}NODE;NODE *createlink(int n){NODE *head=NULL,*p=NULL,*q=NULL;int i=1;head=p=(struct node*)malloc(sizeof(struct node));p->value=i;for(i=2;i<=n;i++){q=(struct node*)malloc(sizeof(struct node));if(q==0) return 0;p->next=q;p=q;p->value=i;}p->next=head;return head;}void jose(NODE *p,int n,int m){int i,j,g=0;NODE *q=NULL;for(i=1;i<=n;i++){for(j=1;j<m;j++){p=p->next;}q=p->next;p->next=q->next;if(g%5==0){g++;printf("\n");}else g++;printf("%3d:%3dout ",i,q->value-1);free(q);}printf("\n");p->next=NULL;}int main( ){int m=0;int n=0;scanf("%d",&m);scanf("%d",&n);NODE *head=NULL;head=createlink(n);jose(head,n,m);return0;2栈和队列的应用#include"stdio.h"#include"string.h"#include"stdlib.h"#define StackSize 100 //假定预分配的栈空间最多为100个元素#define MaxLength 100 //最大的字符串长度typedef int DataType; //假定栈元素的数据类型为整数typedef struct{DataType data[StackSize];int top;}SeqStack;void Initial(SeqStack*S);int IsEmpty(SeqStack*S);int IsFull(SeqStack*S);void Push(SeqStack*S, DataType x);DataType Pop(SeqStack*S);DataType Top(SeqStack*S);void PrintMatchedPairs(char *expr);void main(void){char expr[MaxLength];printf("请输入符号个数小于%d的表达式：\n",MaxLength); gets(expr);printf("括号对是：\n");PrintMatchedPairs(expr);return;}//置栈空void Initial(SeqStack*S){S-> top= -1;}//判断栈是否空int IsEmpty(SeqStack*S){return S-> top== -1;}//判断栈是否满int IsFull(SeqStack*S){return S-> top== StackSize-1;}//进栈void Push(SeqStack*S, DataType x){if(IsFull(S)){printf("栈上溢!");exit(1);}S-> data[++ S-> top]= x;return;}//出栈DataType Pop(SeqStack*S){if(IsEmpty(S)){printf("栈为空！");return -1;}return S-> data[S-> top--];//栈顶指针加1后将x入栈 }//取栈顶元素DataType Top(SeqStack*S){if(IsEmpty(S)){printf("栈为空！");exit(1);}return S-> data[S-> top];}//括号匹配void PrintMatchedPairs(char *expr){SeqStack S;int i , j , length= strlen(expr);Initial(&S);for(i= 1 ; i<= length ; i++){if(expr[i- 1]== '('){Push(&S,i);}else if(expr[i- 1]== ')'){j= Pop(&S);if(j== -1){printf("没有对应第%d个右括号的左括号\n", i); }else{printf("%d %d\n",i,j);}}}while(!IsEmpty(&S)){j= Pop(&S);printf("没有对应第%d个左括号的右括号\n", j);}}3数组的应用#include<stdio.h>#include<stdlib.h>Sturct tuple3tp /*稀疏矩阵的建立和转置*/{Int i,j;Int v;}Sturct sparmattp{Int mu, nu,tu;Sturct tuple3tp data[31];}Struct sparmattp a,b;V oid crt_sparmat(){Int i;Printf("输入稀疏矩阵行值，列值，最大非零元个数："); Scanf("%d%d%d",&a.mu,&a.nu,&a.tu);For("i=1;i<=a.tu;i++){Printf("输入行坐标，列坐标，非零元"）;Scanf("%d%d%d",&a.data[i].i,&a.data[i].j,&a.data[i].v); }}V oid trans_sparmat(){Int col,p,q;B.mu=a.nu;B.nu=a.mu;B.tu=a.tu;If(b.tu！=0）{Q=1;For(col=1;col<=a.nu;col++)For(p=1;p<=a.tu;p++) if(a.data[p].j==col){B.data[q].i=a.data[p].j;B.data[q].j=a.data[p].i;B.data[q].v=a.data[p].v;Q++;}}}Out(struct sparmattp x){Int i,j,k,flag;For(i=1;i<=x.mu;i++){For(j=1;j<=x.nu;j++){Flag=0;For(k=1;k<=x.tu;k++){If(((x.data[k].i)==i)&&((x.data[k].j)==j)){Flag=1;Printf("%5d",x.data[k].v);}}If(flag==0)printf(" 0");}Printf("\n");}}Main( ){Printf("稀疏矩阵的建立与转置\n");Crt_sparmat();Trans_sparmat();Printf("原矩阵为:\n");Out(a);Printf("转置矩阵为:\n"); Out(b);}4数和二叉树的应用#include <stdio.h>#include <stdlib.h>#define maxsize 100typedef char datatype;typedef struct node /*二叉树结点类型*/{datatype data;struct node *lchild,*rchild;} bitree;bitree *Q[maxsize]; /*用于创建二叉树*/bitree *CREATREE(); /*函数声明*/int depth(bitree *);void print(bitree *);void print1(bitree *);void print3(bitree *);int main() /*主函数*/{bitree *Bitree;char ch;while(1){printf(" @@@@@@@@@@@@@@@@本程序的功能是输出普通二叉树的深度@@@@@@@@@@@@@@@\n");printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@02-12-07 23:01@@@@@@\n");Bitree = CREATREE(Bitree); /*生成一棵二叉树*/printf("前序打印：");print(Bitree); /*打印二叉树*/printf("\n中序打印：");print2(Bitree);printf("\n后序打印：");print3(Bitree);printf("\n此二叉树的深度为：");printf("%d\n",depth(Bitree));printf("Input 'q' to quit and 'c' run again:");do{if((ch = getchar()) == 'q' || ch == 'Q')exit(0);}while((ch!='C') && (ch!='c'));system("cls");}return 1;}bitree *CREATREE()/*建立二叉树*/{char ch;int front,rear;bitree *root,*s;root = NULL;front = 1;rear = 0;printf("请按完全二叉树的层次（不是完全二叉树的空结点用'@'补全）从左到右的顺序输入，\n详细请参考help.doc.最后用'#'结束：\n");ch = getchar(); /*按完全二叉树的层次输入，不是完全二叉树的空节点用’@‘补全，最后用’#‘结束*/while(ch != '#'){s = NULL;if(ch !='@') /*节点不为空*/{s = malloc(sizeof(bitree));if(!s){printf("内存分配失败!\n");exit(0);}s->data = ch;s->lchild = NULL;s->rchild = NULL;}rear++;Q[rear] = s; /*Q[rear]指向新分配的节点，Q[front]指向上一个的节点*/ if(rear == 1)root = s; /*S为根*/else{if(s && Q[front]) /*若S为孩子*/if(rear%2 == 0)Q[front]->lchild = s; /*S为左孩子*/elseQ[front]->rchild = s; /*S为右孩子*/if(rear%2 == 1)front++;}ch = getchar();}return root;}void print(bitree *t) /*先序形式输出二叉树*/{if (t){printf(" %c", t->data);print(t->lchild);print(t->rchild);}elsereturn;}print2(bitree *t)/*中序递归遍历二叉树*/{if(t){print2(t->lchild);printf(" %c",t->data);print2(t->rchild);}elsereturn;}void print3(bitree *t) /*后序形式输出二叉树*/ {if (t){print3(t->lchild);print3(t->rchild);printf(" %c", t->data);}elsereturn;}int depth(bitree *t) /*求二叉树深度的算法*/{int dep1, dep2;if (t == NULL) return 0;/*空树*/else{dep1 = depth(t->lchild); /*遍历左子树*/dep2 = depth(t->rchild); /*遍历右子树*/if (dep1 > dep2) /*取深度大者*/return (dep1 + 1);elsereturn (dep2 + 1);}}5图的应用#include <stdio.h>#include <stdlib.h>#include <string.h>struct road{ int st; int ed; int w;}; road all[900];int A[30];int cmp(const void *a,const void *b){ return (*(road *)a).w - (*(road *)b).w;} int find(int x){ if (x != A[x])A[x] = find(A[x]);return A[x];}int main(){ int i,j,k,q,p,m,n,sum;char s,e;while (scanf("%d",&n) != EOF){if (n == 0)break;memset(A,0,sizeof(int));for (i = 1;i <= n;i++)A[i] = i;m = 0;for (i = 1;i < n;i++){ scanf(" %c%d",&s,&p); while (p--){scanf(" %c%d",&e,&q);all[m].st = s - 'A';all[m].ed = e - 'A';all[m].w = q;m++;}}qsort(all,m,sizeof(all[0]),cmp);k = 0;sum = 0;while (k < m){all[k].st = find(all[k].st);all[k].ed = find(all[k].ed);if (all[k].st != all[k].ed){sum += all[k].w;A[all[k].st] = all[k].ed;}k++;}printf("%d\n",sum);}system("pause");return 0;}6查找表的应用struct Stu{char name[MAX_NAME_SIZE];//学生名字char sex; //学生性别char stu_id[STU_ID_SIZE]; //学生证号id};class MyList{public:MyList();bool AppendKey(char *name,int sex,char *stuid); //往链表中添加元素void DeleteKey(char *stuid); //删除表中key的元素bool FindKey(char *stuid); //判断表中是否含key的元素void ShowList(); //显示表中的所有元素~MyList();private:struct LNode{struct Stu stu;struct LNode *next;} *m_Head; //表头};//构造函数MyList::MyList(){//初始化表头m_Head = NULL;}//析构函数MyList::~MyList(){//释放申请的内存空间struct LNode *pNode = m_Head;while(pNode){m_Head = m_Head->next;delete pNode;pNode = m_Head;}}bool MyList::AppendKey(char *name,int sex,char *stuid){struct LNode *pNode;pNode = m_Head;while(pNode)//遍历链表{if(!strcmp(pNode->stu.stu_id,stuid))//先查找表中有无相同的值，如果有相同的就返回falsereturn false;pNode = pNode->next;}//把新的节点插入表头pNode = new struct LNode;pNode->next = m_Head;strcpy(pNode->,name);pNode->stu.sex = sex;strcpy(pNode->stu.stu_id,stuid);m_Head = pNode;return true;}void MyList::DeleteKey(char *stuid){struct LNode *pNode,*pPrev;pNode = m_Head;pPrev = NULL;while(pNode)//遍历整个表{if(!strcmp(pNode->stu.stu_id,stuid)){if(pPrev == NULL){//要删除的是头节点m_Head = m_Head->next;delete pNode;}else{//非头节点pPrev->next = pNode->next;delete pNode;}break;}pPrev = pNode;pNode = pNode->next;}}bool MyList::FindKey(char *stuid){struct LNode *pNode;pNode = m_Head;while(pNode)//遍历整个表{if(!strcmp(pNode->stu.stu_id,stuid))//找到值相同的元素，返回true return true;pNode = pNode->next;}return false;//}void MyList::ShowList(){struct LNode *pNode;pNode = m_Head;while(pNode){printf("%s\t",pNode->stu.stu_id);pNode = pNode->next;}printf("\n\n");}void main(){MyList list;list.AppendKey("aaa",0,"3106001771");list.DeleteKey("3106001771");}7排序算法的应用#include<stdio.h>#include<stdlib.h>#include<time.h>void shell_sort(int arr[],int size) {int i,j,k,temp;for(i=size/2;i>0;i/=2){ for(j=i;j<size;j++){ temp=arr[j];for(k=j-i;k>=0&&temp<arr[k];k-=i){ arr[k+i]=arr[k]; }arr[k+i]=temp;}}/* for(i=0;i<size;i++) { printf("%d ",arr[i]); }*/ }void bubble_sort(int arr[],int size){int i,j,k;for(i=size-1;i>0;i=k){ for(j=0,k=0;j<i;j++){ if(arr[j]>arr[j+1]){ arr[j]^=arr[j+1]^=arr[j]^=arr[j+1];k=j;}}} /* for(i=0;i<size;i++) { printf("%d ",arr[i]); }*/ }void insert_sort(int arr[],int size){int i,j,temp;for(i=1;i<size;i++){temp=arr[i];for(j=i-1;j>=0&&temp<arr[j];j--){ arr[j+1]=arr[j]; }arr[j+1]=temp; }/* for(i=0;i<size;i++) { printf("%d ",arr[i]); }*/}void select_sort(int arr[],int size){int i,j,min;for(i=0;i<size-1;i++){ min=i; for(j=i+1;j<size;j++){ if(arr[j]<arr[min]){ min=j;}}if(min!=i){ arr[min]^=arr[i]^=arr[min]^=arr[i];}} /*for(i=0;i<size;i++){ printf("%d ",arr[i]);}*/}void main(){longstart_select,end_select,start_insert,end_insert,start_bubble,end_bubble,start_shell,end_sh ell;int select[15000],insert[15000],bubble[15000],shell[15000];int i,j;srand((int)time(0));select[0]=rand()%25000+1;for(i=1;i<15000;i++){ select[i]=rand()%25000+1; for(j=0;j<i;j++){ if(select[i]==select[j]){ i--;} } } //printf("随机数组：");for(i=0;i<15000;i++){ shell[i]=bubble[i]=insert[i]=select[i];}//printf("%d ",shell[i]); } printf("\n");printf("下面是选择排序：");start_select=clock();select_sort(select,15000);end_select=clock();printf("\n所用的时间是%ld毫秒\n",(long)(end_select-start_select));printf("\n下面是插入排序：");start_insert=clock();insert_sort(insert,15000);end_insert=clock();printf("\n所用的时间是%ld毫秒\n",(long)(end_insert-start_insert));printf("\n下面是冒泡排序：");start_bubble=clock();bubble_sort(bubble,15000);end_bubble=clock();printf("\n所用的时间是%ld毫秒\n",(long)(end_bubble-start_bubble));printf("\n下面是希尔排序：");start_shell=clock();shell_sort(shell,15000);end_shell=clock();printf("\n所用的时间是%ld毫秒\n",(long)(end_shell-start_shell));。