南邮_数据结构_综合实验
数据结构实验代码
·
实验一：线性表的基本运算及多项式的算术运算
1.顺序表操作
#include <stdio.h>
#include <stdlib.h>
#define Err 0
#define Ok 1
/*
定义顺序表结构体
n代表顺序表元素个数
maxlength代表线性表最大数据长度
Listhead为顺序表内存开辟空间返回的首地址
*/
typedef struct SeqList
{
int n;
int maxLength;
int *Listhead;
} SeqList;
/*
顺序表初始化
使用动态分配数组空间方式构造空线性表
若动态分配一位数字失败，返回Err
时间复杂度O(1)
*/
int Init(SeqList *L, int mSize)
{
L->Listhead = (int *)malloc(mSize * sizeof(int));
//开辟最大长度*单位内存长度的空间返回地址给头指针
L->n = 0;
L->maxLength = mSize;
if (!L->Listhead)
return Err;
return Ok;
}
/*
查找表中ai的值
i下标作为参数传入函数
x参数返回查到的值
先判断表是否为空？下标是否越界？
时间复杂度O(1)
*/
int FindElement(SeqList *L, int i, int *x)
{
if (!L->Listhead)
return Err;
if (i < 0 || i >= L->maxLength)
return Err;
*x = L->Listhead[i];
return Ok;
}
/*
在ai后插入x
顺序表是否已满？下表是否越界？
平均时间复杂度为O(n)
*/
int Insert(SeqList *L, int x, int i)
{
if (L->n == L->maxLength)
return Err; // 溢出
if (i >= L->n-1||i<-1)
return Err; //下标越界
for (int j = L->n - 1; j > i; j--)
{
L->Listhead[j + 1] = L->Listhead[j]; //被插入位置及其后元素全部后移
}
L->Listhead[i+1] = x;
L->n++;
return Ok;
}
/*
将元素ai删除
顺序表是否为空？下标i是否越界？
平均时间复杂度为O(n)
*/
int Delete(SeqList *L, int i)
{
if (!L->n)
return Err;
if (i < 0 || i > L->n-1)
return Err;
for (int j = i + 1; j <=L->n-1; j++)
{
L->Listhead[j - 1] = L->Listhead[j];
}
L->n--;
return Ok;
}
/*
表是否为空？
时间复杂度为O(n)
*/
int Print(SeqList *L)
{
if (L->n==0)
return Err;
for (int j = 0; j < L->n; j++)
{
printf("%d ", L->Listhead[j]);
}
return Ok;
}
/*
释放开辟的顺序表内存空间
时间复杂度为O(1)
*/
int Destory(SeqList *L)
{
L->n = 0;
L->maxLength = 0;
free(L->Listhead);
}
int main()
{
SeqList L;
Init(&L, 10);
for (int i = 0; i < 10; i++)
{
Insert(&L, i , i);
}
Print(&L);
int x;
FindElement(&L, 6, &x);
printf("find: %d", x);
Delete(&L, 3);
printf("\n");
Print(&L);
Destory(&L);
return 0;
}
2.链表操作
#include <stdio.h>
#include <stdlib.h>
#define Elementtype int
#define status int
#define Ok 1
#define Err 0
typedef struct node{
Elementtype element;
struct node* link;
}Node;
typedef struct HeadList{
int n;
Node* headlink;
}HeadList;
status Init(HeadList* L){
Node* p=(Node*)malloc(sizeof(Node));
p->element=0;
p->link=NULL;
L->n=0;
L->headlink=p;
return Ok;
}
status Find(HeadList* L,int i,Elementtype* x){
if(i<0||i>L->n) return Err;
Node* p=L->headlink->link;
for(int j=0;j<i;j++){
p=p->link;
}
*x=p->element;
return Ok;
}
status Insert(HeadList* L,Elementtype x){//insert from head
Node* p=(Node*)malloc(sizeof(Node));
p->element=x;
p->link=L->headlink->link;
L->headlink->link=p;
(L->n)++;
return Ok;
}
status InsertByid(HeadList* L,int i,int x){//insert after i
Node* p=L->headlink->link;
for(int j=0;j<i;j++){
p=p->link;
}
Node* new=(Node*)malloc(sizeof(Node));
new->element=x;
new->link=p->link;
p->link=new;
}
status Delete(HeadList* L,int i){//delete number i
if(i<0||i>L->n) return Err;
if(L->n==0) return Err;
Node* q=L->headlink->link;
Node* p;
for(int j=1;j<i;j++){
q=q->link;
p=q->link;
}
q->link=p->link;
free(p);
return Ok;
}
status Print(HeadList* L){
if(L->n==0) return Err;
Node* p=L->headlink;
while(p->link!=NULL){
printf("%d ",p->link->element);
p=p->link;
}
return Ok;
}
status Destory(HeadList* L){
L->n=0;
Node* p=L->headlink;
while(!p->link){
Node* m=p->link;
free(p->link);
p=m;
}
free(L->headlink);
}
status Reverse(HeadList* L){
Node* back=L->headlink->link;
Node* e0=L->headlink->link;
Node* mid=back->link;
while(e0->link!=NULL){
back=L->headlink->link;
e0->link=mid->link;
mid->link=back;
L->headlink->link=mid;
mid=e0->link;
}
}
status Sort(HeadList* L){
Node* p=L->headlink;
Node* q=p->link;
while(p->link!=NULL){
q=p->link;
while(q!=NULL){
if(q->element<p->element){
Elementtype temp=p->element;
p->element=q->element;
q->element=temp;
}
q=q->link;
}
p=p->link;
}
}
int main(){
HeadList L;
Init(&L);
for(int i=4;i<=7;i++){
Insert(&L,i);
}
for(int i=3;i>=1;i--){
Insert(&L,i);
}
Print(&L);
printf("\n");
Reverse(&L);
Print(&L);
printf("\n");
Sort(&L);
Print(&L);
printf("\n");
Delete(&L,4);
Print(&L);
printf("\n");
InsertByid(&L,3,9);
Print(&L);
printf("\n");
int x;
Find(&L,5,&x);
printf("%d",x);
Destory(&L);
return 0;
}3.多项式
#include <stdio.h>
#include <stdlib.h>
#define status int
#define Ok 1
#define Err 0
typedef struct pNode{
int coef;
int exp;
struct pNode* link;
}PNode;
typedef struct polynominal{
PNode* head;
}Polynominal;
void Create(Polynominal* p){
PNode *pn,*pre,*q;
p->head=(PNode*)malloc(sizeof(PNode));
p->head->exp=-1;
p->head->link=p->head;//? for loop node
for (;;){
pn = (PNode *)malloc(sizeof(PNode));
printf("coef and exp: (input)\n");
scanf("%d %d", &pn->coef, &pn->exp);
//printf("exp: (input)\n");
//scanf("%d", &pn->exp);
if(pn->exp<0)
break;
pre = p->head;
q = p->head->link;
while(q->exp>pn->exp){
pre = q;
q = q->link;
}
pn->link = q;
pre->link = pn;
}
}
void Init(Polynominal* p){
p->head=(PNode*)malloc(sizeof(PNode));
p->head->exp=-1;
p->head->link=p->head;
}
void Insert(Polynominal* p,int coef,int exp){
PNode* new = (PNode *)malloc(sizeof(PNode));
new->coef = coef;
new->exp = exp;
PNode *pre = p->head;
PNode *back = pre->link;
while(back->exp>new->exp){
pre = back;
back = back->link;
}
new->link = back;
pre->link = new;
}
void Add(Polynominal* px,Polynominal* qx){
PNode *q, *q1, *p, *temp;
p = px->head->link;
q1 = qx->head;
q = q1->link;
while(p->exp>=0){
while(p->exp<q->exp){
q1 = q;
q = q->link;
}
if(p->exp==q->exp){
q->coef = q->coef + p->coef;
if(q->coef==0){
q1->link = q->link;
free(q);
p = p->link;
q = q1->link;
}else{
q1 = q;
q = q->link;
p = p->link;
}
}else{
temp = (PNode *)malloc(sizeof(PNode));
temp->coef = p->coef;
temp->exp = p->exp;
q1->link = temp;
temp->link = q;
p = p->link;
q1 = q1->link;
}
}
}
void Destory(Polynominal* p){
PNode *q = p->head->link;
while(q!=p->head){
q = q->link;
q->link = NULL;
free(q);
}
free(p->head);
}
void multipy(Polynominal* x,Polynominal* y,Polynominal* z){
PNode *p = x->head->link;
PNode *q = y->head->link;
while(p->exp>=0){
q = y->head->link;
while(q->exp>=0){
int coef = (p->coef) * (q->coef);
int exp = p->exp + q->exp;
Insert(z,coef,exp);
q = q->link;
}
p = p->link;
}
}
void Print(Polynominal* x){
PNode *p = x->head->link;
while(p->link!=x->head){
printf("%dx^%d+", p->coef, p->exp);
p = p->link;
}
printf("%dx^%d", p->coef, p->exp);
printf("\n");
}
void combine(Polynominal* x){
PNode *p = x->head->link;
PNode *q = p->link;
while(p->exp>=0){
q = p->link;
while(q->exp>=0){
if(p->exp==q->exp){
p->coef = p->coef + q->coef;
p->link = q->link;
//q->link = NULL;
free(q);
q = p->link;
}else{
break;
}
}
p = p->link;
}
}
int main(){
Polynominal x1, x2, x3;
printf("start write polynominal 1:");
Create(&x1);
printf("start write polynominal 2:");
Create(&x2);
printf("polynominal 1:\t");
Print(&x1);
printf("polynominal 2:\t");
Print(&x2);
Init(&x3);
multipy(&x1, &x2, &x3);
printf("end of multy1:\t");
Print(&x3);
combine(&x3);
printf("end of multy2:\t");
Print(&x3);
Add(&x1, &x2);
printf("end of add:\t");
Print(&x2);
return 0;
}
实验二：二叉树的基本操作及哈夫曼编码/译码系统的实现
1.二叉树先序构建后续遍历求高度节点个数交换子树
#include<stdio.h>
#include<stdlib.h>
#define Elementype int
//二叉树结点结构体
typedef struct btnode{
Elementype element;
struct btnode* lChild;
struct btnode* rChild;
}BTNode;
//二叉树结构体
typedef struct binarytree{
BTNode* root;
}BinaryTree;
//先序遍历
void PreOrder(BTNode* t){
if(!t)
return;
printf("%c",t->element);
PreOrder(t->lChild);
PreOrder(t->rChild);
}
void PreOrderTree(BinaryTree* bt){
PreOrder(bt->root);
}
//中序遍历
void MidOrder(BTNode* t){
if(!t)
return;
MidOrder(t->lChild);
printf("%c",t->element);
MidOrder(t->rChild);
}
void MidOrderTree(BinaryTree* bt){
MidOrder(bt->root);
}
//后序遍历
void AfterOrder(BTNode* t){
if(!t)
return;
AfterOrder(t->lChild);
AfterOrder(t->rChild);
printf("%c",t->element);
}
void AfterOrderTree(BinaryTree* bt){
AfterOrder(bt->root);
}
//先序创建
BTNode* PreCreateBT(BTNode* t){
char ch;
ch=getchar();
if(ch=='#')
t=NULL;
else{
t=(BTNode*)malloc(sizeof(BTNode));
t->element=ch;
t->lChild=PreCreateBT(t->lChild);
t->rChild=PreCreateBT(t->rChild);
}
return t;
}
void PreMakeTree(BinaryTree* bt){
printf("please input ch:");
bt->root=PreCreateBT(bt->root);
}
//二叉树高度
int DepthBT(BTNode* t){
if(t==NULL)
return 0;
int lh, rh;
lh = DepthBT(t->lChild);
rh = DepthBT(t->rChild);
if(lh>rh)
return lh+1;
else
return rh+1;
}
int DepthTree(BinaryTree* bt){
return DepthBT(bt->root);
}
//求二叉树节点个数
int NumberBT(BTNode* t){
if(!t)
return 0;
return NumberBT(t->lChild)+NumberBT(t->rChild)+1;
}
int NumberTree(BinaryTree* bt){
return NumberBT(bt->root);
}
//交换子树
void ExchangeBT(BTNode* t){
if(!t)
return;
if(t->lChild!=NULL||t->rChild!=NULL){
int temp = t->lChild;
t->lChild = t->rChild;
t->rChild = temp;
ExchangeBT(t->lChild);
ExchangeBT(t->rChild);
}
}
void ExchangeTree(BinaryTree* bt){
ExchangeBT(bt->root);
}
int main(){
BinaryTree tree;
PreMakeTree(&tree);
printf("先序遍历:");
PreOrderTree(&tree);
printf("中序遍历:");
MidOrderTree(&tree);
printf("后序遍历:");
AfterOrderTree(&tree);
int hight=DepthTree(&tree);
printf("二叉树高度:%d",hight);
int num=NumberTree(&tree);
printf("二叉树结点个数:%d",num);
ExchangeTree(&tree);
printf("交换子树先序遍历:");
PreOrderTree(&tree);
return 0;
}2.哈夫曼树
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define ElemenType int
//有序单链表
typedef struct hfmTNode{
int w;//存储整形权重
ElemenType element;
struct Link *next;//指向直接后继元素的指针
struct Link *lchild;
struct Link *rchild;
}HFMTNode;
//初始化链表
HFMTNode* InitLink(){
HFMTNode* link = (HFMTNode*)malloc(sizeof(HFMTNode));//创建头结点
link->next = NULL;//头结点的next为空
link->lchild = link->rchild = NULL;
return link;
}
//排序插入元素
void InsertLink(HFMTNode* link,HFMTNode* node){
HFMTNode* p = link;
HFMTNode* q = p->next;
while(q && node->w>q->w)
{
p=q;//记录位置
q=q->next;
}
node->next = q;
p->next = node;
}
//删除节点,返回被删除的节点
HFMTNode* DelLink(HFMTNode* link,int index){
HFMTNode *p, *s;
int i = 0;
p = link;
while(i<index-1 && p->next != NULL) //搜索指定位置前一个节点
{
i++;
p = p->next;
}
if(i != index-1 || p->next == NULL)
printf("删除位置非法");
s = p->next;
p->next = s->next;
return s;
}
//打印有序链表
void PrintLink(HFMTNode* link){
HFMTNode* p = link->next;
while(p){
printf("(%d,%d)",p->element,p->w);
p = p->next;
}
printf("\n");
}
//打印树
void PrintTree(HFMTNode* BT){
if (BT != NULL)
{
printf("%d", BT->w); //输出根结点的值
if (BT->lchild != NULL || BT->rchild != NULL)
{
printf("(");
PrintTree(BT->lchild); //输出左子树
if (BT->rchild != NULL)
printf(",");
PrintTree(BT->rchild); //输出右子树
printf(")");
}
}
}
//创建哈夫曼树
HFMTNode* CreateHuffManTree(HFMTNode* link,int n){
HFMTNode *del1,*del2,*p;
HFMTNode* node ;
int w_sum,i;
p = link;
for(i=0;i<n-1;i++){
del1 = DelLink(p,1);//最小的元素
del2 = DelLink(p,1);//第二小的元素
w_sum = del1->w + del2->w; //两个最小的数的和
node = (HFMTNode*)malloc(sizeof(HFMTNode));
node->lchild= del1;
node->rchild= del2;
node->w = w_sum;
InsertLink(link,node);
}
return node;
}
//哈夫曼编码
void getCoding(HFMTNode *tree,int len){
if(!tree)
return;
static int a[20]; //定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一
int i;
if(!tree->lchild && !tree->rchild){//叶子节点
printf(" %d的哈夫曼编码为：",tree->element);
for(i = 0; i < len; i++)
printf("%d",a[i]);
printf("\n");
}
else{//访问到非叶子结点时分别向左右子树递归调用，并把分支上的0、1编码保存到数组a的对应元素中，向下深入一层时len值增1
a[len] = 0;
getCoding(tree->lchild, len + 1);
a[len] = 1;
getCoding(tree->rchild, len + 1);
}
}
//哈夫曼解码
void DQ(int arrlen,int arr[],HFMTNode *parent){
for (int i = 0; i < arrlen; i++){
deCoding(parent, 0, arr[i]);
}
}
void deCoding(HFMTNode *tree,int len,int alpha){//len=0
static int b[20];
if(!tree->lchild&&!tree->rchild){//叶节点break
if(tree->element==alpha){//???
for (int j = 0; j < len;j++){
printf("%d", b[j]);
}
}
}else{//如果是非叶节点
b[len] = 0;
deCoding(tree->lchild, len + 1,alpha);
b[len] = 1;
deCoding(tree->rchild, len + 1,alpha);
}
}
int main(){
HFMTNode* link = InitLink();//初始化链表
HFMTNode* tree;
int num,w,i,len,element;//长度;
printf("输入元素个数:");
scanf("%d",&num);getchar();
for(i=0;i<num;i++){
printf("第%d个元素的字符:",i+1);
scanf("%d",&element);getchar();
printf("第%d个元素的权重:",i+1);
scanf("%d",&w);getchar();
HFMTNode* node = (HFMTNode*)malloc(sizeof(HFMTNode));;
node->element = element;node->w = w;
InsertLink(link,node);
}
printf("******************\n");
tree = CreateHuffManTree(link,num);
printf("哈夫曼树:");
PrintTree(tree);printf("\n");
getCoding(tree,0);
printf("******************\n");
printf("想要解码的字符串，输入字符个数+1：");
scanf("%d",&len);
int arr[len];
printf("input string:");
for (int i=0; i < len;i++){
scanf("%d", &arr[i]); //一开始携程%d了
}
DQ(len,arr,tree);
return 0;
}
实验三：图的基本运算及智能交通中的最佳路径
1.邻接矩阵实现
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define true 1
#define false 0
typedef struct mGraph{
ElemType **a; //邻接矩阵数组
int n;//顶点数
int e;//边数
ElemType noEdge;//无边时的权值
} MGraph;
typedef struct queue{
int front;
int last;
int num;
int length;
int *arr;
} queue;
void Init(queue* que,int length){
que->length = length;
que->arr = (int *)malloc(sizeof(int) * que->length);
que->front = 0;
que->last = 0;
que->num = 0;
for (int i = 0; i < length;i++){
que->arr[i] = 0;
}
}
void enqueue(queue* que,int value){
que->last = (que->last + 1) % que->length;
que->arr[que->last ] = value;
que->num ++;
}
int dequeue(queue* que){
que->front = (que->front + 1) % que->length;
que->num --;
return que->arr[que->front];
}
int isempty(queue que){
if(que.num+1==que.length)
return 1;
return 0;
}
void destory(queue* que){
free(que->arr);
}
void printque(queue que){
printf("print que...");
int i = (que.front + 1) % que.length;
while(i!=(que.last+1)%que.length){
printf("%d ", que.arr[i]);
i = (i + 1) % que.length;
}
}
//1.初始化边和顶点数2.创建二维数组并初始化边的权值
void InitGraph(MGraph* graph,int verNum,int edgeNum,int noEdge){
graph->e = edgeNum;
graph->n = verNum;
graph->noEdge = noEdge;
graph->a = (ElemType **)malloc(sizeof(ElemType *) * graph->n);
for (int i = 0; i < graph->n;i++){
graph->a[i] = (ElemType *)malloc(sizeof(ElemType) * graph->n);
for (int j = 0; j < graph->n;j++){
graph->a[i][j] = noEdge;
}
graph->a[i][i] = 0;//graph[i][i] = 0;而且，把graph用.了
}
}
void printGraph(MGraph* graph){
printf("\n");
for (int i = 0; i < graph->n;i++){
for (int j = 0; j < graph->n;j++){
printf("%d ", graph->a[i][j]);
}
printf("\n");
}
//printf("%d,%d", graph->n, graph->e);
}
void inputCode(MGraph* graph){
int u, v, w;
printf("\n");
printf("input:");
scanf("%d %d %d", &u, &v, &w);
while(w){
if(u<0||v<0||u>graph->n-1||v>graph->n-1||u==v){
printf("error!");
}else{
graph->a[u][v] = w;
}
scanf("%d %d %d", &u, &v, &w);
}
}
//在哪个图里找？找什么边？
//1.有没有超范围2.查找，找到了返回ture，没找到返回false
int findEdge(MGraph graph,int u,int v){
if(u<0||v<0||u>graph.n||v>graph.n||u==v){
printf("break the arr!");
return false;
}
if(graph.a[u][v]==graph.noEdge){
return false;
}else{
return true;
}
}
void destoryGraph(MGraph* graph){
for (int i = 0; i < graph->n;i++){
free(graph->a[i]);
}
free(graph->a);
}
void deletEdge(MGraph* graph,int u,int v){//边数没变。。。
if(!findEdge(*graph,u,v)){
printf("dont have this egde:(%d,%d)",u,v);
}else{
graph->a[u][v] = graph->noEdge;
}
}
void insertEdge(MGraph* graph,int u,int v,int w){
if(!findEdge(*graph,u,v)){
graph->a[u][v] = w;
}else{
printf("already have egde:(%d,%d)",u,v);
}
}
//1.先把此节点标记为以访问2.访问此节点的未访问邻接点
void DFS(MGraph* graph,ElemType* visited,int i){
visited[i] = 1;
printf("%d ", i);
for (int j = 0; j < graph->n;j++){
if(visited[j]==0&&graph->a[i][j]!=graph->noEdge&&graph->a[i][j]!=0){
DFS(graph, visited, j);
}
}
}
void DFSgraph(MGraph* graph){
ElemType *visited = (ElemType *)malloc(sizeof(ElemType) * graph->n);
for (int i = 0; i < graph->n;i++){
visited[i] = 0;
}
for (int j = 0; j < graph->n;j++){
if(visited[j]==0){
DFS(graph, visited,j);
}
}
free(visited);
}
void BFS(MGraph* graph,ElemType* visited,int v){
visited[v] = 1;
queue que;
Init(&que,10);
printf("%d ", v);
enqueue(&que, v);
while(!isempty(que)){
int p=dequeue(&que);
for (int j = 0; j < graph->n; j++)
{
if (graph->a[p][j] != graph->noEdge && visited[j] == 0)
{
visited[j] = 1;
printf("%d ", j);
enqueue(&que, j);
}
}
}
}
void BFSgraph(MGraph* graph){
ElemType *visited = (ElemType *)malloc(sizeof(ElemType) * graph->n);
for (int i = 0; i < graph->n;i++){
visited[i] = 0;
}
for (int j = 0; j < graph->n;j++){
if(visited[j]==0){
BFS(graph, visited, j);
}
}
free(visited);
}
int main(){
MGraph m;
InitGraph(&m, 7, 10,99);
printGraph(&m);
inputCode(&m);
printf("赋值后：\n");
printGraph(&m);
int a=findEdge(m, 1, 3);
printf("\n");
printf("查找结果：%d",a);
printf("\n");
insertEdge(&m, 2, 1,9);
printGraph(&m);
deletEdge(&m, 3, 1);
printGraph(&m);
DFSgraph(&m);
printf("\n");
BFSgraph(&m);
destoryGraph(&m);
// queue que;
// Init(&que, 10);
// enqueue(&que, 1);
// enqueue(&que, 2);
// enqueue(&que, 3);
// enqueue(&que, 4);
// printque(que);
// int a=dequeue(&que);
// printf("a:%d ", a);
// int b=dequeue(&que);
// printf("b:%d ", b);
// printque(que);
// printf("empty? %d ", isempty(que));
// destory(&que);
return 0;
}
2.邻接表
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
//结点
typedef struct eNode{
int adjVex;
ElemType w;
struct eNode *nextArc;
} ENode;
//邻接表
typedef struct lGraph{
int n;
int e;
ENode **a;
} LGraph;
typedef struct queue{
int front;
int last;
int num;
int length;
int *arr;
} queue;
void Init(queue* que,int length){
que->length = length;
que->arr = (int *)malloc(sizeof(int) * que->length);
que->front = 0;
que->last = 0;
que->num = 0;
for (int i = 0; i < length;i++){
que->arr[i] = 0;
}
}
void enqueue(queue* que,int value){
que->last = (que->last + 1) % que->length;
que->arr[que->last ] = value;
que->num ++;
}
int dequeue(queue* que){
que->front = (que->front + 1) % que->length;
que->num --;
return que->arr[que->front];
}
int isempty(queue que){
if(que.num+1==que.length)
return 1;
return 0;
}
void destory(queue* que){
free(que->arr);
}
void printque(queue que){
printf("print que...");
int i = (que.front + 1) % que.length;
while(i!=(que.last+1)%que.length){
printf("%d ", que.arr[i]);
i = (i + 1) % que.length;
}
}
void Initlg(LGraph* lg,int nSize){
lg->n = nSize;
lg->e = 0;
lg->a = (ENode **)malloc(sizeof(ENode)*nSize);
for (int i = 0; i < nSize;i++){
lg->a[i] = NULL;
}
}
int Exist(LGraph* lg,int u,int v){
if(u==v||u<0||v<0||u>lg->n||v>lg->n)
return 0;
ENode *p = lg->a[u];
while(p&&p->adjVex!=v)
p = p->nextArc;
if(!p){return 0;}else{
return 1;
}
}
int Insert(LGraph* lg,int u,int v,ElemType w){
if(u==v||u<0||v<0||u>lg->n||v>lg->n)
return 0;
if(Exist(lg,u,v)){
printf("重复！");
return 0;
}
ENode *p = (ENode *)malloc(sizeof(ENode));
p->adjVex = v;
p->w = w;
p->nextArc = lg->a[u];
lg->a[u] = p;
lg->e++;
return 1;
}
void print(LGraph* lg){
for (int i = 0; i < lg->n;i++){
ENode *p = lg->a[i];
while(p){
printf("(%d,%d)", i, p->adjVex);
p = p->nextArc;
}
}
}
int delete(LGraph* lg,int u,int v){
if(u==v||u<0||v<0||u>lg->n||v>lg->n)
return 0;
if(!Exist(lg,u,v)){
printf("边不存在！");
return 0;
}
ENode *p = lg->a[u];
ENode *q = NULL;//this
while(p&&p->adjVex!=v){
q = p;
p = p->nextArc;//this sequence
}
if(!p){return 0;}
if(q){
q->nextArc = p->nextArc;
}
else{lg->a[u] = p->nextArc;}
//free(p);
lg->e--;
return 1;
}
void destorylg(LGraph* lg){
ENode *p, *q;
for (int i = 0; i < lg->n;i++){
p = lg->a[i];
q = lg->a[i];
while(p){
p = p->nextArc;
free(q);
q = p;
}
}
free(lg->a);
}
void DFS(LGraph* lg,ElemType* visited,int i){
visited[i] = 1;
printf("%d ", i);
ENode *p = lg->a[i];
while(p){
DFS(lg, visited, p->adjVex);
p = p->nextArc;
}
}
void DFSgraph(LGraph* lg){
ElemType *visited = (ElemType *)malloc(sizeof(ElemType) * lg->n);
for (int i = 0; i < lg->n;i++){
visited[i] = 0;
}
for (int j = 0; j < lg->n;j++){
if(visited[j]==0){
DFS(lg, visited,j);
}
}
free(visited);
}
void BFS(LGraph* lg,ElemType* visited,int v){
visited[v] = 1;
queue que;
Init(&que,10);
printf("%d ", v);
enqueue(&que, v);
while(!isempty(que)){
int p=dequeue(&que);
ENode *q = lg->a[p];
while(q&&visited[q->adjVex]==0){
printf("%d ", q->adjVex);
visited[q->adjVex] = 1;
enqueue(&que, q->adjVex);
q = q->nextArc;
}
}
}
void BFSgraph(LGraph* lg){
ElemType *visited = (ElemType *)malloc(sizeof(ElemType) * lg->n);
for (int i = 0; i < lg->n;i++){
visited[i] = 0;
}
for (int j = 0; j < lg->n;j++){
if(visited[j]==0){
BFS(lg, visited, j);
}
}
free(visited);
}
int main(){
LGraph lg;
Initlg(&lg, 4);
Insert(&lg, 0, 1, 1);
Insert(&lg, 1, 3, 1);
//delete(&lg, 2, 1);
Insert(&lg, 3, 2, 1);
print(&lg);
DFSgraph(&lg);
BFSgraph(&lg);
destorylg(&lg);
}3.最佳路径
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct mGraph{
int n;
int e;
int noedge ;
ElemType **a;
} mGraph;
void InitGraph(mGraph* graph,int verNum,int edgeNum,int noedge){
graph->e = edgeNum;
graph->n = verNum;
graph->noedge = noedge;
graph->a = (ElemType **)malloc(sizeof(ElemType *) * graph->n);
for (int i = 0; i < graph->n;i++){
graph->a[i] = (ElemType *)malloc(sizeof(ElemType) * graph->n);
for (int j = 0; j < graph->n;j++){
graph->a[i][j] = noedge;
}
graph->a[i][i] = 0;//graph[i][i] = 0;而且，把graph用.了
}
}
void inputCode(mGraph* graph){
int u, v, w;
printf("\n");
printf("input:");
scanf("%d %d %d", &u, &v, &w);
while(w!=-1){
if(u<0||v<0||u>graph->n-1||v>graph->n-1||u==v){
printf("error!");
}else{
graph->a[u][v] = w;
}
scanf("%d %d %d", &u, &v, &w);
}
}
void destoryGraph(mGraph* graph){
for (int i = 0; i < graph->n;i++){
free(graph->a[i]);
}
free(graph->a);
}
void Floyd(mGraph g){
printf("floyd:\n");
ElemType **d = (ElemType **)malloc(g.n * sizeof(ElemType *));//a
int **p = (int **)malloc(g.n * sizeof(int *));
for (int i = 0; i < g.n;i++){
d[i] = (ElemType *)malloc(g.n * sizeof(ElemType));
p[i] = (int *)malloc(g.n * sizeof(int));
for (int j = 0; j < g.n;j++){
d[i][j] = g.noedge;
p[i][j] = 0;
}
}//初始化
for (int i = 0; i < g.n;i++){
for (int j = 0; j < g.n;j++){
d[i][j] = g.a[i][j];
if(i!=j&&d[i][j]<g.noedge)
p[i][j] = i;
else
p[i][j] = -1;
}
}
for (int k = 0; k < g.n;k++){
for (int i = 0; i < g.n;i++){
for (int j = 0; j < g.n;j++){
if(d[i][j]>d[i][k]+d[k][j]){
d[i][j] = d[i][k] + d[k][j];
p[i][j] = p[k][j];
}
}
}
}
for (int i = 0; i < g.n;i++){
for (int j = 0; j < g.n;j++){
printf("%d ", d[i][j]);
}
printf("\n");
}
}
int main(){
mGraph g;
InitGraph(&g, 4, 10,100);
inputCode(&g);
Floyd(g);
return 0;
}
实验四：各种内排序算法的实现及性能比较
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#define KeyType int
#define DataType int
typedef struct entry
{
KeyType key;
DataType data;
} Entry;
typedef struct list
{ // pay attention!100
int n;
Entry D[100000];
} List;
typedef struct maxheap
{
int n, Maxsize;
Entry D[100000];
} MaxHeap;
void initlist(List *list, int n)
{
list->n = n;
int b[n], i, j;
for (i = 0; i < n; i++)
b[i] = i;
srand(time(NULL));
for (i = 0; i < n; i++)
{
j = (int)((float)((n - i) * rand()) / (RAND_MAX + 1.0));
list->D[i].key = b[j];
b[j] = b[n - 1 - i];
}
FILE *p = fopen("D.txt","w");
if(p)
{
fputs("D数组key：\t",p);
for (int m = 0; m < n; m++)
{
fprintf(p, "%d", list->D[m].key);
putc(' ',p);
}
fclose(p);
}
}
//简单选择排序
void exchange(List *list, int i, int j)
{
if (i == j)
return;
Entry temp = list->D[i];
list->D[i] = list->D[j];
list->D[j] = temp;
}
int findmin(List list, int findfrom)
{
int i, min = findfrom;
for (i = findfrom + 1; i < list.n; i++)
{
if (list.D[i].key < list.D[min].key)
{
min = i;
}
}
return min;
}
void choseSort(List list)
{
for (int i = 0; i < list.n; i++)
{
int minindex = findmin(list, i);
exchange(&list, i, minindex);
}
printf("\n选择排序：\t");
print(list);
// FILE *p = fopen("ChoseSort.txt","w");
// if(p)
// {
// fputs("chosesort：\t",p);
// for (int m = 0; m < list.n; m++)
// {
// fprintf(p, "%d", list.D[m].key);
// putc(' ',p);
// }
// fclose(p);
// }
}
void print(List list)
{
for (int i = 0; i < list.n; i++)
{
printf("%d ", list.D[i].key);
}
}
void inserSort(List list)
{
double start1 = clock();
int j;
Entry insertitem;
for (int i = 1; i < list.n; i++)
{
insertitem = list.D[i];
for (j = i - 1; j >= 0; j--)
{
if (insertitem.key < list.D[j].key)
{
list.D[j + 1] = list.D[j];
}
else
{
break;
}
}
list.D[j + 1] = insertitem;
}
print(list);
// FILE *p = fopen("InserSort.txt","w");
// if(p)
// {
// fputs("插入排序：\t",p);
// for (int m = 0; m < list.n; m++)
// {
// fprintf(p, "%d", list.D[m].key);
// putc(' ',p);
// }
// fclose(p);
// }
double stop1 = clock();
double duration = ((double)(stop1 - start1)) / CLK_TCK;
printf("\ttime:%f", duration);
}
void bubblesort(List list)
{
double start1 = clock();
for (int i = 0; i < list.n - 1; i++)
{
for (int j = list.n - 1; j > i; j--)
{
if (list.D[j].key < list.D[j - 1].key)
{
Entry temp = list.D[j];
list.D[j] = list.D[j - 1];
list.D[j - 1] = temp;
}
}
}
print(list);
// FILE *p = fopen("Bubble.txt","w");
// if(p)
// {
// fputs("冒泡排序：\t",p);
// for (int m = 0; m < list.n; m++)
// {
// fprintf(p, "%d", list.D[m].key);
// putc(' ',p);
// }
// fclose(p);
// }
}
void Swap(Entry *D, int i, int j)
{
Entry temp;
if (i == j)
return;
temp = *(D + i);
*(D + i) = *(D + j);
*(D + j) = temp;
}
int Partition(List *list, int low, int high)
{
int i = low, j = high + 1;
Entry pivot = list->D[low];
do
{
do
{
i++;
} while (i <= high && list->D[i].key < pivot.key);
do
{
j--;
} while (list->D[j].key > pivot.key);
if (i < j)
{
Swap(list->D, i, j);
}
} while (i < j);
Swap(list->D, low, j);
return j;
}
void QuickSort(List *list, int low, int high)
{
int k;
if (low < high)
{
k = Partition(list, low, high);
QuickSort(list, low, k - 1);
QuickSort(list, k + 1, high);
}
}
void Quick(List *list)
{
QuickSort(list, 0, list->n - 1);
printf("\n快速排序：\t");
}
void Merge(List *list, Entry *temp, int low, int n1, int n2)
{
int i = low, j = low + n1;
while (i <= low + n1 - 1 && j <= low + n1 + n2 - 1)
{
if (list->D[i].key <= list->D[j].key)
{
*temp++ = list->D[i++];
}
else
{
*temp++ = list->D[j++];
}
}
while (i <= low + n1 - 1)
{
*temp++ = list->D[i++];
}
while (j <= low + n1 + n2 - 1)
{
*temp++ = list->D[j++];
}
}
void MergeSort(List *list, int temp_maxsize)
{
Entry temp[temp_maxsize];
int low, n1, n2, i, size = 1;
while (size < list->n)
{
low = 0;
while (low + size < list->n)
{
n1 = size;
if (low + size * 2 < list->n)
n2 = size;
else
n2 = list->n - low - size;
Merge(list, temp + low, low, n1, n2);
low += n1 + n2;
}
for (i = 0; i < low; i++)
list->D[i] = temp[i];
size *= 2;
}
printf("\n两路合并：\t");
}
void HeapSort(MaxHeap *hp)
{
int i;
Entry temp;
for (i = (hp->n - 2) / 2; i >= 0; i--)
AdjustDown(hp->D, i, hp->n - 1);
for (i = hp->n - 1; i > 0; i--)
{
Swap(hp->D, 0, i);
AdjustDown(hp->D, 0, i - 1);
}
printf("\n堆排序：\t");
}
void AdjustDown(MaxHeap *hp, int current, int broder)
{
int p = current;
int maxchild;
Entry temp;
while (2 * p + 1 <= broder)
{ //非叶节点
if ((2 * p + 2 <= broder) && hp->D[2 * p + 1].key > hp->D[2 * p + 2].key)
{
maxchild = 2 * p + 1;
}
else
{
maxchild = 2 * p + 2;
} //选中左右节点中较大的那个
if (hp->D[p].key <= hp->D[maxchild].key)
break;
else
{
temp = hp->D[p];
hp->D[p] = hp->D[maxchild];
hp->D[maxchild] = temp;
p = maxchild;
}
}
}
int main()
{
List list;
double time[6];
int arrsize = 70000;
initlist(&list, arrsize);
double start1 = clock();
choseSort(list);
double stop1 = clock();
double duration = ((double)(stop1 - start1)) / CLK_TCK;
printf("\ttime:%f", duration);
time[0] = duration;
double start2 = clock();
inserSort(list);
double stop2 = clock();
duration = ((double)(stop2 - start2)) / CLK_TCK;
printf("\ttime:%f", duration);
time[1] = duration;
double start3 = clock();
bubblesort(list);
double stop3 = clock();
duration = ((double)(stop3 - start3)) / CLK_TCK;
printf("\ttime:%f", duration);
time[2] = duration;
double start4 = clock();
Quick(&list);
print(list);
double stop4 = clock();
duration = ((double)(stop4 - start4)) / CLK_TCK;
printf("\ttime:%f", duration);
time[3] = duration;
double start5 = clock();
MergeSort(&list, arrsize);
print(list);
double stop5 = clock();
duration = ((double)(stop5 - start5)) / CLK_TCK;
printf("\ttime:%f", duration);
time[4] = duration;
MaxHeap hp;
hp.Maxsize = arrsize;
hp.n = arrsize;
for (int i = 0; i < arrsize; i++)
{
hp.D[i].key = list.D[i].key;
}
double start6 = clock();
HeapSort(&hp);
print(list);
double stop6 = clock();
duration = ((double)(stop6 - start6)) / CLK_TCK;
printf("\ttime:%f", duration);
time[5] = duration;
printf("\n");
for (int i = 0; i < 6;i++){
printf("%lf ", time[i]);
}
#include <stdio.h>
FILE *p = fopen("a.txt","w");
if(p)
{
putc('h',p);
fclose(p);
}
return 0;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
4
0- 0
已为社区贡献1条内容
所有评论(0)