数据结构-C语言
AI-摘要
切换
Tianli GPT
AI初始化中...
介绍自己
生成本文简介
推荐相关文章
前往主页
前往tianli博客
数据结构-C语言
以下代码是博主学习期间的代码,有什么疑问或者补充请在下面评论区留言😄😄😄
1.顺序表
//2022.9.1 顺序表
#include<stdio.h>
#include<stdlib.h>
#define N 20
typedef struct sqlist
{
int *elem; //基地址
int length; //线性表长度
int listsize; //存储空间的大小
}sql;
//定义一个变量(顺序表)
sql L;
//初始化
void InitList()
{
L.elem=(int *)malloc(N*sizeof(int)); //获取整型需要的存储空间
if(!L.elem)
exit(0); //空间申请失败,退出
L.listsize=N; //空间大小
L.length=0; //空间长度
}
//输入
void input(int n)
{
int i;
printf("输入数组的值:");
for(i=0;i<n;i++)
scanf("%d",&L.elem[i]);
L.length=n;
}
//输出
void output()
{
int i;
for(i=0;i<L.length;i++)
printf("%d ",L.elem[i]);
printf("\n");
}
//插入
void insertNode(int i,int e) //插入节点
{
int *p,*q,k=i;
q=L.elem+i-1;
if(k<0||k>L.length+1)
{
printf("超出范围无法插入\n");
exit(0);
}
if(L.length>=L.listsize)
{
printf("存储空间不足!!!\n");
exit(0);
/*
newbase=(int *)realloc(L.elem,(N+M)*sizeof(int)) //追加存储空间
if(!newbase)
exit(0);
L.elem=newbase:
L.listsize+=M;*/
}
for (p = L.elem+L.length-1; p >=q ; p--)
*(p+1)=*p; //移动元素
*q=e;
L.length++;
}
//删除
int delNode(int i)
{
int *p,*q;
int e;
q=L.elem+i-1;
e=*q;
for(p=q+1;p<=L.elem+L.length-1;p++)
*(p-1)=*p;
L.length--;
return e;
}
void main()
{
int n,i=3,e=7;
InitList();
printf("输入n的值:");
scanf("%d",&n);
input(n);
printf("插入前的值:");
output();
insertNode(3,7);
printf("插入后的值:");
output();
delNode(4);
printf("删除后的值:");
output();
}2.单链表-正序
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}node;
node *l,*t;
void initlist(){
l=(node *)malloc(sizeof (node));
if (!l)
exit(0);
l->next=NULL;
t=l;
}
void creat(int n){
node *p;
int i;
for (i=1;i<=n;i++)
{
p=(node *)malloc(sizeof (node));
if (!p)
exit(0);
scanf("%d",&p->data);
p->next=NULL;
t->next=p;
t=p;
}
}
void output(){
node *p;
p=l->next;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
printf ("\n");
}
void main(){
int n;
initlist();
printf("请输入链表长度:");
scanf("%d",&n);
printf("请输入元素:");
creat(n);
printf("输出结果:\n");
output();
}3.单链表
//2022.9.13链式表
#include <stdio.h>
#include <stdlib.h>
typedef struct link
{
int data;//代表数据域
struct link *next;//代表指针域,指向后继元素
}link;//link为节点名,每个节点都是一个link结构体
//定义头指针
link *L;
//初始化链表
void Initlink(){
L=(link*)malloc(sizeof(link));//创建首元节点
L->next=NULL;//创建头指针
}
//创建单链表
void creatlink(int n){
link *p;
Initlink();
int i;
for(i=1;i<=n;i++){
p=(link*)malloc(sizeof(link));
scanf("%d",&p->data);
p->next=L->next;
L->next=p;
}
}
//遍历(输出访问)
void output(){
link *p;
p=L->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
//插入
void insertlink(int i,int e){
link *p,*s;
p=L;
int j=0;
while(j<i-1&&p)
{
p=p->next;
j++;
}
if(j>i-1||!p) //是否合法
{
printf("插入位置不存在:\n");
exit(0);
}
s=(link *)malloc(sizeof(link)); //在插入地方分配内存
s->data=e;
s->next=p->next;
p->next=s;
}
//删除
int dellink(int i){
link *p,*q;
int j,e;
p=L;
j=0;
while(j<i-1&&p->next){
p=p->next;
j++;
}
if(j>i-1||!p->next) //是否合法
{
printf("插入位置不存在:\n");
exit(0);
}
q=p->next;
e=q->data;
p->next=q->next;
free(q); //释放已分配的内存
return e;
}
void main(){
int i,e,n,x;
Initlink();
printf("请输入像创建的元素个数:");
scanf("%d",&n);
printf("请输入元素:");
creatlink(n);
printf("输出结果为:");
output();
printf("\n输入插入位置:");
scanf("%d",&i);
printf("输入插入的值:");
scanf("%d",&e);
insertlink(i,e);
printf("输出插入后的结果:");
output();
printf("\n请输入删除的值位置:");
scanf("%d",&x);
printf("返回删除的值:");
printf("%d",dellink(x));
}4.单链表-多个
//2022.9.28 建立多个正序单链表并合并
#include<stdio.h>
#include<stdlib.h>
typedef struct node {
int data;
struct node* next;
}node;
node* initlist() {
node* l, * t;
l = (node*)malloc(sizeof(node));
if (!l)
exit(0);
l->next = NULL;
t = l;
return l;//返回头指针
}
//创建链表
void creat(node* l, int n) {
node* p, * t;
t = l;
int i;
for (i = 1; i <= n; i++)
{
p = (node*)malloc(sizeof(node));
if (!p)
exit(0);
scanf("%d", &p->data);
p->next = NULL;
t->next = p;
t = p;
}
}
//历遍(输出)
void output(node* l) {
node* p;
p = l->next;
while (p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
//合并链表
node* merge(node* l1, node* l2) {
node* p, * i, * j, * t;
i = l1->next;
j = l2->next;
//比较两个链表第一个节点的大小
if(i->data<=j->data){
t = l1;
}
else {
t = l2;
}
//将头节点给临时变量p
p = t;
while (i && j) {
if (i->data < j->data)//判断那一个作为第一个节点
{
p->next = i;
p = i;
i = i->next;
}
else {
p->next = j;
p = j;
j = j->next;
}
//如果其中一个链表较长将剩余的加在后面
if (i) {
p->next = i;
}
else if(j)
{
p->next = j;
}
}
return t;
}
void main() {
int n, m;
node* l1, * l2, * l;
l1 = initlist();
l2 = initlist();
printf("请输入l1链表的长度:");
scanf("%d", &n);
printf("请输入了l1中的元素:");
creat(l1, n);
printf("输出l1的结果:\n");
output(l1);
printf("请输入l2链表的长度:");
scanf("%d", &m);
printf("请输入了l2中的元素:");
creat(l2, m);
printf("输出l2的结果:\n");
output(l2);
l = merge(l1, l2);
printf("输出合并链表l的值:\n");
output(l);
}5.邻接表
#include <stdio.h>
#include <stdlib.h>
#define N 20
typedef struct link
{
int data;//代表数据域
struct link *next;//代表指针域,指向后继元素
}link;//link为节点名,每个节点都是一个link结构体
link *b[N];//头节点
//创建
void creat(int n){
int u,v;
link *p;
for(u=0;u<n;u++)
b[u]=NULL;
scanf("%d%d",&u,&v);
while(u>=0)
{
p=(link*)malloc(sizeof(link));
p->data=v;
p->next=b[u];
b[u]=p;
scanf("%d%d",&u,&v);
}
}
//遍历
void output(int n){
link *p;
int u;
for(u=0;u<n;u++)
{
printf("%5d",u);
p=b[u];
while(p)
{
printf("%5d",p->data);
p=p->next;
}
printf("\n");
}
}
void main(){
creat(6);
printf("邻接表为:\n");
output(6);
}6.双向链表
//2022.9.16双向链表
#include<stdio.h>
#include<stdlib.h>
typedef struct dlink{
int data;//代表数据域
struct dlink *prior,*next;//prior代表前驱,next代表后继
}dlink;//双链表节点名
dlink *L;
//初始化链表
void initlink()
{
L=(dlink *)malloc(sizeof(dlink));
L->next=NULL;
L->prior=NULL;
}
//创建双向链表
void creatlink(int n){
dlink *p;
initlink();
int i;
for(i=1;i<=n;i++){
p=(dlink*)malloc(sizeof(dlink));
scanf("%d",&p->data);
p->next=L->next;
L->next=p;
p->prior=L;
L->next->prior=p;
}
}
//遍历(输出访问)
void output(){
dlink *p;
p=L->next;
while(p)
{
printf("%d ",p->data);
p=p->next;
}
}
//插入
void insertlink(int i,int e){
dlink *p,*s;
p=L;
int j=0;
while(j<i-1&&p){
p=p->next;
j++;
}
if(j>i-1||!p)
{
printf("插入位置不存在:\n");
exit(0);
}
s=(dlink *)malloc(sizeof(dlink));
s->data=e;
s->next=p->next;
s->prior=p;
p->next=s;
p->next->prior=s;
}
//删除
int dellink(int i){
dlink *p,*q;
int j,e;
p=L;
j=0;
while(j<i-1&&p->next){
p=p->next;
j++;
}
if(j>i-1||!p->next) //是否合法
{
printf("插入位置不存在:\n");
exit(0);
}
q=p->next;
e=q->data;
p->next=q->next;
q->next->prior=p;
free(q); //释放已分配的内存
return e;
}
void main(){
int n,i,e,x;
initlink();
printf("请输入像创建的元素个数:");
scanf("%d",&n);
printf("请输入元素:");
creatlink(n);
printf("输出结果为:");
output();
printf("\n输入插入位置:");
scanf("%d",&i);
printf("输入插入的值:");
scanf("%d",&e);
insertlink(i,e);
printf("输出插入后的链表:");
output();
printf("\n请输入删除的值位置:");
scanf("%d",&x);
printf("返回删除的值:");
printf("%d",dellink(x));
printf("\n返回删除后的链表:");
output();
}7.栈
//2020.9.23栈
#include <stdio.h>
#include <stdlib.h>
#define N 20
//定义顺序栈的类型
typedef struct sqstack{
int *base; //栈底指针
int *top; //栈顶指针
int stacksize; //存储空间大小
}sqs;
sqs s; //定义一个顺序栈
//初始化
void initstack(){
s.base=(int *)malloc(N*sizeof(int));
if(!s.base)
exit(0);
s.top=s.base; //空栈
s.stacksize=N;
}
//入栈(插入元素)
void push(int e){
if(s.top-s.base>=s.stacksize){
printf("栈满\n");
exit(0);
/*s.base=(int *)realloc(s.base,(N+M)*sizeof(int))
if(!s.base) exit(0);
s.top=s.base+s.stacksize;
s.stacksize+=M;
*/
}
*s.top=e; //插入
s.top++; //修改栈顶指针
}
//出栈(删除)
int pop(){
int e;
if(s.top==s.base){
printf("空栈\n");
exit(0);
}
s.top--;//修改栈顶指针
e=*s.top;//赋值
return e;
}
//数值转换
void conversion(){
int n,x;
initstack();
printf("请输入十进制数:");
scanf("%d",&n);
while(n)
{
x=n%2;
push(x);
n=n/2;
}
printf("转换为二进制数:");
while(s.top!=s.base)
printf("%d",pop());
printf("\n");
}
void main(){
int e,n;
initstack();
printf("请输入入栈元素个数:");
scanf("%d",&n);
printf("请输入入栈元素:");
for(int i=1;i<=n;i++){
scanf("%d",&e);
push(e);
}
printf("返回删除的值:");
while(s.top!=s.base)
printf("%d ",pop());
printf("\n");
conversion();
}8.队列
//2022.9.27 队列
//队列的特点,插入在队尾,删除在队前,先进先出.
#include <stdio.h>
#include <stdlib.h>
//定义单链表节点类型
typedef struct qlink{
int data; //数据域
struct qlink *next;//指针域
}qlink;
//定义链队列的类型
typedef struct linkqueue{
qlink *front;//队头指针
qlink *rear;//队尾指针
}linkq;
linkq q;//定义一个链队列
//初始化链队列
void initqlink(){
q.front=(qlink *)malloc(sizeof(qlink));
if (!q.front)
exit(0);
q.front->next=NULL;
q.rear=q.front;//空队列
}
//入队(插入)
void enqlink(int e){
qlink *p;
p=(qlink *)malloc(sizeof(qlink));
if (!p)
exit(0);
p->data=e;
p->next=NULL;
q.rear->next=p;//连接作用
q.rear=p;//修改队尾指针
}
//出队(删除)
int deqlink(){
qlink *p;
int x;
if(q.rear==q.front){
printf("空队列,不进行删除\n");
exit(0);
}
p=q.front->next;
x=p->data;
q.front->next=p->next;
if(p==q.rear)//如果队尾指针没有,空队列
q.rear=q.front;
free(p);
return x;
}
void main(){
int e,n;
initqlink();
printf("请输入创建的队列的长度:\n");
scanf("%d",&n);
printf("请输入元素:\n");
for(int i=1;i<=n;i++){
scanf("%d",&e);
enqlink(e);
}
printf("返回删除的值:");
while(q.rear!=q.front){
printf("%d ",deqlink());
}
}9.回文-数值
//2022.9.28 回文的实现(数值)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//定义单链表节点类型
typedef struct qlink {
int data; //数据域
struct qlink* next;//指针域
}qlink;
//定义链队列的类型
typedef struct linkqueue {
qlink* front;//队头指针
qlink* rear;//队尾指针
}linkq;
linkq q;//定义一个链队列
//初始化链队列
void initqlink() {
q.front = (qlink*)malloc(sizeof(qlink));
if (!q.front)
exit(0);
q.front->next = NULL;
q.rear = q.front;//空队列
}
//入队(插入)
void enqlink(int e) {
qlink* p;
p = (qlink*)malloc(sizeof(qlink));
if (!p)
exit(0);
p->data = e;
p->next = NULL;
q.rear->next = p;//连接作用
q.rear = p;//修改队尾指针
}
//出队(删除)
int deqlink() {
qlink* p;
int x;
if (q.rear == q.front) {
printf("空队列,不进行删除\n");
exit(0);
}
p = q.front->next;
x = p->data;
q.front->next = p->next;
if (p == q.rear)//如果队尾指针没有,空队列
q.rear = q.front;
free(p);
return x;
}
#define N 20
//定义顺序栈的类型
typedef struct sqstack {
int* base; //栈底指针
int* top; //栈顶指针
int stacksize; //存储空间大小
}sqs;
sqs s; //定义一个顺序栈
//初始化
void initstack() {
s.base = (int*)malloc(N * sizeof(int));
if (!s.base)
exit(0);
s.top = s.base; //空栈
s.stacksize = N;
}
//入栈(插入元素)
void push(int e) {
if (s.top - s.base >= s.stacksize) {
printf("栈满\n");
exit(0);
/*s.base=(int *)realloc(s.base,(N+M)*sizeof(int))
if(!s.base) exit(0);
s.top=s.base+s.stacksize;
s.stacksize+=M;
*/
}
*s.top = e; //插入
s.top++; //修改栈顶指针
}
//出栈(删除)
int pop() {
int e;
if (s.top == s.base) {
printf("空栈\n");
exit(0);
}
s.top--;//修改栈顶指针
e = *s.top;//赋值
return e;
}
//判断是否为回文
void judge() {
int e, n, x = 0, y = 0;
initstack();
initqlink();
printf("请输入数值长度:");
scanf("%d", &n);
printf("请输入数值:");//逐个输入元素
for (int i = 1; i <= n; i++) {
scanf("%d", &e);
push(e);
enqlink(e);
}
int b = n;//第一个循环n--到0了,需要将n赋给另一个变量
while (s.top != s.base)
{
x = x + pop() * pow(10,n);
n--;
}
printf("输出x的值");
printf("%d", x/10);//将各个元素合在一起化成数值
printf("\n");
while (q.rear != q.front)
{
y = y + deqlink() * pow(10, b );
b--;
}
printf("输出y的值");
printf("%d", y/10);//将各个元素合在一起化成数值
printf("\n");
if (x == y)//比较是否相等判断是否为回文
printf("该数值是回文");
else
printf("该数值不是回文");
}
/*这里面有个问题,就是pow()里面的n如果等于n-1的话出来的结果不正确,不知道为什么,
在vs studio里面是正常的,但只要把他变成n,在输出的时候再除上一个10就行了*/
void main() {
judge();
}10.回文-字符
//2022.9.28 回文的实现(字符)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//定义单链表节点类型
typedef struct qlink {
int data; //数据域
struct qlink* next;//指针域
}qlink;
//定义链队列的类型
typedef struct linkqueue {
qlink* front;//队头指针
qlink* rear;//队尾指针
}linkq;
linkq q;//定义一个链队列
//初始化链队列
void initqlink() {
q.front = (qlink*)malloc(sizeof(qlink));
if (!q.front)
exit(0);
q.front->next = NULL;
q.rear = q.front;//空队列
}
//入队(插入)
void enqlink(char e) {
qlink* p;
p = (qlink*)malloc(sizeof(qlink));
if (!p)
exit(0);
p->data = e;
p->next = NULL;
q.rear->next = p;//连接作用
q.rear = p;//修改队尾指针
}
//出队(删除)
char deqlink() {
qlink* p;
char x;
if (q.rear == q.front) {
printf("空队列,不进行删除\n");
exit(0);
}
p = q.front->next;
x = p->data;
q.front->next = p->next;
if (p == q.rear)//如果队尾指针没有,空队列
q.rear = q.front;
free(p);
return x;
}
#define N 20
//定义顺序栈的类型
typedef struct sqstack {
int* base; //栈底指针
int* top; //栈顶指针
int stacksize; //存储空间大小
}sqs;
sqs s; //定义一个顺序栈
//初始化
void initstack() {
s.base = (int*)malloc(N * sizeof(int));
if (!s.base)
exit(0);
s.top = s.base; //空栈
s.stacksize = N;
}
//入栈(插入元素)
void push(char e) {
if (s.top - s.base >= s.stacksize) {
printf("栈满\n");
exit(0);
/*s.base=(int *)realloc(s.base,(N+M)*sizeof(int))
if(!s.base) exit(0);
s.top=s.base+s.stacksize;
s.stacksize+=M;
*/
}
*s.top = e; //插入
s.top++; //修改栈顶指针
}
//出栈(删除)
char pop() {
char e;
if (s.top == s.base) {
printf("空栈\n");
exit(0);
}
s.top--;//修改栈顶指针
e = *s.top;//赋值
return e;
}
//判断是否为回文
void judge() {
char e;
int n;
initstack();
initqlink();
printf("请输入第一个字符串长度和元素:");//直接输入不要有空格
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
e = getchar();
push(e);
enqlink(e);
}
printf("是否为回文:");
while (s.top != s.base&& q.rear != q.front)//判断是否为回文,因为长度都相同所以要存在都存在,要不存在都不存在
{
if (pop() != deqlink())
printf("NO");
else
{
printf("YES");
break;
}
}
}
void main() {
judge();
}11.循环队列
//2022.9.30循环队列
#include <stdio.h>
#include <stdlib.h>
#define N 20
//定义顺序队列的类型
typedef struct sqque
{
int *base;//基地址
int front;//队头指针(下标)
int rear;//队尾指针(下表)
}sqq;
//定义一个顺序队列
sqq q;
void initque(){
q.base=(int *)malloc(N*sizeof(int));
if(!q.base)
exit();
q.front=q.rear=0;//空队列
}
//入队
void enque(int e)
{
if(q.front==(q.rear+1)%N)
{
exit(0);
}
q.base[q.rear]=e;//元素的插入
q.rear=(q.rear+1)%N;//修改的队尾指针
}
//出队
void delque(){
int e;
if(q.base==q.rear)
{
exit(0);
}
e=q.rear[q.front];
q.front=(q.front+1)%N;//修改队头指针
return e;
}12.三元组顺序表
//2022.10.11
#include <stdio.h>
#include <stdlib.h>
#define N 20
//定义三元组类型
typedef struct triple
{
int i,j;//行列下标
int e;//非零元的值
}triple;
//定义三元组顺序表的类型
typedef struct TS{
triple data[N+1];
int mu,nu,tu;//行数,列数,非零元个数
}TS;
TS M,T;//定义一个三元组顺序表
//三元组表的建立
void creat(){
int r,c,x;M.tu=0;//行 列 值 下表
printf("请输入稀疏矩阵的行数和列数:");
scanf("%d%d",&M.mu,&M.nu);
printf("请输入值:");
for(r=1;r<=M.mu;r++)
for(c=1;c<=M.nu;c++)
{
scanf("%d",&x);
if(x)
{
M.tu++;
M.data[M.tu].i=r;
M.data[M.tu].j=c;
M.data[M.tu].e=x;
}
}
}
//转置三元组表
void fasttrans(){
int num[N],cpot[N],col,p,q;
T.nu=M.mu;
T.mu=M.nu;
T.tu=M.tu;
if(T.tu)
{
for(col=1;col<=M.nu;col++)
num[col]=0;
for(p=1;p<=M.tu;p++)
{
col=M.data[p].j;
num[col]++;
}
cpot[1]=1;
for(col=2;col<=M.nu;col++)
cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=M.tu;p++)
{
col=M.data[p].j;
q=cpot[col];
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
cpot[col]++;
}
}
}
//输出
void output(TS A)
{
int p;
for(p=1;p<=A.tu;p++)
printf("%3d%3d%3d\n",A.data[p].i,A.data[p].j,A.data[p].e );
}
void main(){
creat();
printf("输出转置前的:\n");
output(M);
printf("输出转置后的:\n");
fasttrans();
output(T);
}13.二分查找
//2022.12.2二分查找
#include<stdio.h>
#include<stdlib.h>
#define N 20
typedef struct sqlist
{
int *elem;
int length;
int listsize;
}sql;
sql L;
void InitList()
{
L.elem=(int *)malloc(N*sizeof(int));
if(!L.elem)
exit(0);
L.listsize=N;
L.length=0;
}
void input(int n)
{
int i;
printf("请输入值:");
for(i=1;i<=n;i++)
scanf("%d",&L.elem[i]);
L.length=n;
}
void output()
{
int i;
for(i=1;i<=L.length;i++)
printf("%d ",L.elem[i]);
printf("\n");
}
int x=0;
int binsearch(int key)
{
int low,high,mid;
low=1;
high=L.length;
while (low<=high)
{
x++;
mid=(low+high)/2;
if (key<L.elem[mid])
high=mid-1;
else if (key==L.elem[mid])
return mid;
else
low=mid+1;
}
return 0;
}
int main()
{
int n,key;
InitList();
printf("请输入个数:");
scanf("%d",&n);
input(n);
output();
printf("请输入要查找的值:\n");
scanf("%d",&key);
if (binsearch(key)!=0)
printf("查找成功,在:%d的位置",binsearch(key));
else
printf("查找失败!");
printf("%d",x);
return 0;
}14.深度搜索
#include <stdio.h>
#include <stdlib.h>
#define N 20
typedef struct link
{
int data;//代表数据域
struct link *next;//代表指针域,指向后继元素
}link;//link为节点名,每个节点都是一个link结构体
link *b[N];//头节点
//定义链队列的类型
typedef struct linkqueue{
link *front;//队头指针
link *rear;//队尾指针
}linkq;
linkq q;//定义一个链队列
//初始化链队列
void initqlink(){
q.front=(link *)malloc(sizeof(link));
if (!q.front)
exit(0);
q.front->next=NULL;
q.rear=q.front;//空队列
}
//入队(插入)
void enqlink(int e){
link *p;
p=(link *)malloc(sizeof(link));
if (!p)
exit(0);
p->data=e;
p->next=NULL;
q.rear->next=p;//连接作用
q.rear=p;//修改队尾指针
}
//出队(删除)
int deqlink(){
link *p;
int x;
if(q.rear==q.front){
printf("空队列,不进行删除\n");
exit(0);
}
p=q.front->next;
x=p->data;
q.front->next=p->next;
if(p==q.rear)//如果队尾指针没有,空队列
q.rear=q.front;
free(p);
return x;
}
//创建邻接链表
void creat(int n){
int u,v;
link *p;
for(u=0;u<n;u++)
b[u]=NULL;
scanf("%d%d",&u,&v);
while(u>=0)
{
p=(link*)malloc(sizeof(link));
p->data=v;
p->next=b[u];
b[u]=p;
scanf("%d%d",&u,&v);
}
}
//遍历
void output(int n){
link *p;
int u;
for(u=0;u<n;u++)
{
printf("%5d",u);
p=b[u];
while(p)
{
printf("->");
printf("%2d",p->data);
p=p->next;
}
printf("\n");
}
}
//深度优先搜索
int vst[N]={0};
void dfs(int u){
link *p;
int v;
printf("%d ",u);
vst[u]=1; //已被访问
p=b[u];
while(p)
{
v=p->data;
if(vst[v]==0)
dfs(v); //递归
p=p->next;
}
}
//广度优先搜索
int bvst[N]={0};
void bsf(int u){
link *p;
int v,x;
printf("%d ",u);
bvst[u]=1;
enqlink(u);
while(q.front!=q.rear){
v=deqlink();
p=b[v];
while (p)
{
x=p->data;
if(bvst[x]==0){
printf("%d ",x);
bvst[x]=1;
enqlink(x);
}
p=p->next;
}
}
}
void main(){
initqlink();
creat(6);
printf("邻接表为:\n");
output(6);
printf("深度优先搜索结果:");
dfs(0);
printf("\n");
printf("广度优先搜索结果:");
bsf(0);
}15.二叉树
#include<stdio.h>
#include<stdlib.h>
//定义二叉链表节点的类型
typedef struct bitnode {
char data;
struct bitnode* lchild, * rchild;
}bitnode;
//先建立二叉链表
bitnode* creat() {
bitnode* T;
char ch;
scanf("%c", &ch);
if (ch == '.')
return NULL;
else
{
T = (bitnode*)malloc(sizeof(bitnode));
if (!T)
exit(0);
T->data = ch; //按照根左右的顺序建立
T->lchild = creat();
T->rchild = creat();
return T;
}
}
//先序遍历
void preorder(bitnode* T) {
if (T)
{
printf("%c", T->data); //访问根
preorder(T->lchild);
preorder(T->rchild);
}
}
//中序遍历
void inorder(bitnode* T) {
if (T) {
inorder(T->lchild);
printf("%c", T->data);
inorder(T->rchild);
}
}
//后序遍历
void postorder(bitnode* T) {
if (T) {
inorder(T->lchild);
inorder(T->rchild);
printf("%c", T->data);
}
}
//子叶个数
int leafsum(bitnode* T) {
if (!T) //如果没有元素则没有叶子节点
return 0;
else if (!T->rchild && !T->lchild) //如果都没有左孩子和右孩子返回1
return 1;
else
return leafsum(T->lchild) + leafsum(T->rchild); //若其他情况继续递归执行函数
}
//先序求结点个数
int n=0;
void count(bitnode *T){
if(T)
{
n++;
count(T->lchild);
count(T->rchild);
}
}
//后序求二叉树的深度
int depth(bitnode *T){
int h,l,r;
if(!T)
h=0;
else
{
l=depth(T->lchild);
r=depth(T->rchild);
h=(l>r?l:r)+1;
}
return h;
}
void main() {
bitnode* root;
printf("请输入二叉树:");
root = creat();
printf("先序建立结果:");
preorder(root);
printf("\n先序建立结果:");
inorder(root);
printf("\n先序建立结果:");
postorder(root);
printf("\n叶子结点的总数:");
printf("%d", leafsum(root));
count(root);
printf("\n结点的个数为:%d",n);
printf("\n树的深度为:%d",depth(root));
}16.哈夫曼树
#include<stdio.h>
#define N 100
#define HUGE 100
//定义哈夫曼树的结点类型
typedef struct hnode {
int weight; //权值
int parent; //双亲
int lchild; //左孩子
int rchild; //右孩子
}hnode;
hnode h[N]; //存放所有节点
int w[N] = { 0 }; //存放权值
//输入叶子结点的个数和权值
int n, m;
void input() {
printf("请输入叶子的个数:");
scanf("%d", &m);
printf("请输入%d个叶子结点的权值:", m);
for (int i = 0; i < m; i++)
scanf("%d", &w[i]);
n = 2 * m - 1; //所有节点的个数
}
//初始化,说明
void init() {
for (int i = 0; i < n; i++)
{
h[i].weight = w[i];
h[i].parent = -1;
h[i].lchild = -1;
h[i].rchild = -1;
}
}
int minmun() {
int min, k;
min = w[0];
k = 0;
for (int i = 0; i < n; i++)
if (w[i] < min && w[i] != 0)
{
min = w[i];
k = i;
}
w[k] = HUGE; //把挑走的值改掉,防止重复挑选
return k;
}
void creat() {
int l, r;//最小值下标
for (int i = m; i < n; i++)
{
l = minmun();
r = minmun();
h[i].lchild = l;
h[i].rchild = r;
h[i].weight = h[l].weight + h[r].weight;
h[l].parent = i;
h[r].parent = i;
w[i] = h[i].weight;
}
}
void output() {
for (int i = 0; i < n; i++)
printf("%5d%5d%5d%5d%5d\n", i, h[i].weight, h[i].parent, h[i].lchild, h[i].rchild);
}
void main()
{
input();
init();
creat();
printf(" 下标 权值 双亲 左孩子 右孩子\n");
printf("-----------------------------------------\n");
output();
}- 感谢你赐予我前进的力量
-
微信 
支付宝
赞赏者名单
因为你们的支持让我意识到写文章的价值🙏
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 窝窝头
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
