单链表，二叉树，图，查找和排序的程序设计

C语言
数据结构
发布日期:   2020-03-06
文章字数:   3.8k
阅读时长:   17 分
阅读次数:  

1 单链表设计

要求：

(1)建立单向链表，表长任意；

(2)可交互输出单链表中的内容；

(3)编写算法计算出自己所建单链表的长度并输出；

(4)删除自己所建单链表中的第K个结点，并将剩余结点输出；

(5)将单链表倒排，输出结果。

程序：

#include <stdio.h>  
#include <stdlib.h>
//定义链表中的节点  
struct node
{  
    unsigned char data;//链表中的数据     
    struct node * next;//指向下一节点的指针  
};

//变量定义
struct node  *p,*p1,*p2,*head;

//函数声明 
void ListCreate();
void ListTraverse();
void ListLength();
int ListDelete();
int ListReverse();

//主函数  
int main()
{ 
    ListCreate();        //单向链表的建立  
    ListTraverse();      //单向链表的输出 
    ListLength();        //单向链表长度计算 
    ListDelete();        //单向链表结点的删除 
    ListReverse();      //单链表的倒排 
}

//单向链表的建立 
void ListCreate()
{        
    head=p=(struct node * )malloc(sizeof(struct node)); 
    printf("请输入链表数据元素值(0为结束标志,中间不能用任何符号)：\n");      
    scanf("%c",&p->data);//头结点的数据成员      
    while(p->data!='0')//给出0结束条件,退出循环    
    {       
        p1=p;        
        p=(struct node * )malloc(sizeof(struct node));        
        scanf("%c",&p->data);//中间结点数据成员       
        p1->next=p;//中间结点的指针成员值    
    }      
    p->next=NULL;//尾结点的指针成员值  
}

//单向链表的输出 
void ListTraverse()
{      
    p=head;     
    printf("\n链表数据成员是：");      
    while(p->next!=NULL)      
    {        
        printf("%c  ",p->data);  //输出成员数据       
        p=p->next;      
    }    
}

//单向链表长度计算 
void ListLength()
{    
    p2=head->next;    
    int  j=1;            //j用来存放链表的长度    
    while((p2->data)-48)    
    {      
        p2=p2->next;      
        j++;    
    }    
    printf("\n链表长度是:  %d",j);
}

//单向链表结点的删除 
int ListDelete()
{    
    p2 = head;
    int j = 1,M,K;        
    printf("\n要删除第几个节点: "); 
    scanf("%d",&K);
    if ( j > (K-1)) //删除头节点   
    {       
        struct node  *p3;      
        p3=p2;      
        p2=p3->next;    
    }    
    else   //删除其它节点     
    {    
        while ((p2->next)-48 && j < (K-1))  
        {        
            p2 = p2->next;        
            ++j;    
        }     
        if (p2->next == NULL )  
        {         
            printf("Position Error\n");        
            return 0;    
        }    
        struct node *temp = p2->next;  //执行删除操作    
        p2->next = temp->next;    
    }        
    p=head;     
    printf("删除后的链表数据成员是：");      
    while(p->next!=NULL)      
    {        
        printf("%c  ",p->data);  //输出成员数据       
        p=p->next;      
    }  
}

//单链表的倒排
int ListReverse()
{    
    struct node *h,*h1,*h2;    
    h=head;    
    h1=h;                         
    h=NULL;    
    while(h1->next!=NULL)      //通过循环使h从最后一个元素依次向前    
    {          
        h2 = h1->next;          
        h1->next = h;          
        h = h1;          
        h1 = h2;    
    }       
    printf("\n倒排后的链表数据成员是：");      
    while(h!=NULL)  //输出数据元素    
    {        
        printf("%c  ",h->data);        
        h=h->next;      
    }   
}

难点：单链表的倒排，这里有两种方法实现

1）逆序单链表的循环算法：

LINK_NODE *ReverseLink(LINK_NODE *head)
{
    LINK_NODE *next;
    LINK_NODE *prev = NULL;

    while(head != NULL)
    {
        next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }

    return prev;
}

2）逆序单链表的递归算法：

LINK_NODE *ReverseLink2(LINK_NODE *head)
{
    LINK_NODE *newHead;

    if((head == NULL) || (head->next == NULL))
        return head;

    newHead = ReverseLink2(head->next); /*递归部分*/
    head->next->next = head; /*回朔部分*/
    head->next = NULL;

    return newHead;
}

我们该选择循环还是递归？

根据问题的类型和规模作出选择。对于线性数据结构，比较适合用迭代循环方法，而对于树状数据结构，比如二叉树，递归方法则非常简洁优雅。

2 二叉树设计

要求：
(1)动态交互建立二叉树，结点个数任意；

(2)分别用DLR,LDR,LRD三种方式对二叉树进行遍历，并输出结果；

(3)计算二叉树中的结点个数并输出；

(4)计算二叉树的深度并输出。

程序:

#include <stdio.h>
#include <stdlib.h> 

//节点声明，数据域、左指针、右指针
typedef struct BiTNode
{   
    int data;//二叉树数据元素    
    struct BiTNode *Left,*Right;//二叉树左右指针 
}BiTNode,*BiTree;

//函数声明 
int CreateBiTree(BiTNode **T);
void DLR_BiTree(BiTNode *T); 
void LDR_BiTree(BiTNode *T);
void LRD_BiTree(BiTNode *T);
int BiTreeCount(BiTNode *T);
int BiTreeDeep(BiTNode *T); 

//主函数 
int main()
{   
    BiTree T;   
    int depth,Count = 0;      
    printf("请输入第一个节点的值(0表示没有该节点)： ");   
    CreateBiTree(&T);//二叉树建立   
    printf("\n");      
    printf("先序遍历二叉树：");   
    DLR_BiTree(T);//二叉树先序遍历    
    printf("\n");      
    printf("中序遍历二叉树：");   
    LDR_BiTree(T);//二叉树中序遍历    
    printf("\n");      
    printf("后序遍历二叉树：");   
    LRD_BiTree(T);//二叉树后序遍历    
    printf("\n");      
    Count = BiTreeCount(T);//求二叉树结点个数      
    printf("二叉树结点个数：%d\n",Count);        
    depth = BiTreeDeep(T);//求二叉树深度     
    printf("二叉树的深度为：%d\n",depth);
}

//先序创建二叉树  
int CreateBiTree(BiTNode **T)  
{     
    int ch;      
    scanf("%d",&ch);//给二叉树第一个节点赋值      
    if (ch == 0)      
    {          
        *T = NULL;  //输入为0表示没有该节点         
        return 0;      
    }      
    else      
    {          
        *T = (BiTNode *)malloc(sizeof(BiTNode));  //给二叉树节点分配内存         
        if (T == NULL)          
        {              
            printf("failed\n");              
            return 0;          
        }          
        else          
        {              
            (*T)->data = ch;              
            printf("输入%d的左子节点：",ch);              
            CreateBiTree(&((*T)->Left));  //递归给二叉树左节点赋值             
            printf("输入%d的右子节点：",ch);              
            CreateBiTree((&(*T)->Right)); //递归给二叉树右节点赋值         
        }      
    }        
    return 1;  
} 

//二叉树先序遍历
void DLR_BiTree(BiTNode *T)
{ 
    if( T == NULL) return;//递归调用的结束条件  
    printf("%d",T->data);//访问节点的数据域  
    DLR_BiTree(T->Left);//先序递归遍历左子树  
    DLR_BiTree(T->Right);//先序递归遍历右子树 
}

//二叉树中序遍历     
void LDR_BiTree(BiTNode *T)
{ 
    if(T==NULL) return;//递归调用的结束条件 
    LDR_BiTree(T->Left);//中序递归遍历左子树 
    printf("%d",T->data);//访问节点的数据域 
    LDR_BiTree(T->Right);//中序递归遍历右子树
}

//二叉树后序遍历 
void LRD_BiTree(BiTNode *T)
{ 
    if(T==NULL) return;//递归调用的结束条件 
    LRD_BiTree(T->Left);//后序递归遍历左子树 
    LRD_BiTree(T->Right);//后序递归遍历右子树 
    printf("%d",T->data);//访问节点的数据域
}

//求二叉树结点个数 
int BiTreeCount(BiTNode *T)
{    
    if(T==NULL)        
        return 0;//空二叉树结点数为0    
    else                                    
        return BiTreeCount(T->Left)+BiTreeCount(T->Right)+1;//左右子树结点总数加1
} 

//求二叉树深度 
int BiTreeDeep(BiTNode *T)  
{      
    int deep = 0;      
    if (T != NULL)      
    {          
        int leftdeep = BiTreeDeep(T->Left);//递归得到左子树深度          
        int rightdeep = BiTreeDeep(T->Right);//递归得到右子树深度         
        deep = leftdeep >= rightdeep?leftdeep+1:rightdeep+1;//比较得到二叉树深度      
    }        
    return deep;  
}

3 图的设计

要求：

(1)根据书本上算法，完成图的深度和广度优先遍历，要求任意给定起始点，输出结果。

(2)根据书本上算法，完成图的单元最短路径的算法，要求任意给定源点，输出结果。

程序：

#include <stdio.h>
#include <stdlib.h>

#define MAXVEX  100  //最大顶点数  
#define INFINITY 65535//用65535来代表无穷大  

//定义访问标记 
int visited[MAXVEX]={0};  

//定义图结构体  
typedef struct  
{  
    char vexs[MAXVEX];//顶点表  
    int  arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边  
    int  numVertexes, numEdges;   //图中当前的顶点数和边数  
}Graph;   

//辅助数组中的元素定义  
typedef struct 
{  
    int distance;  
    int path[MAXVEX];  
}ArrayNode;

//函数声明
void CreateGraph(Graph *g);
void DFS(Graph g,int v);
void BFS(Graph g,int v);
void SHORT(Graph *g,int from,int to);
void SHORT(Graph *g,int from,int to);

//主函数 
int main()
{
    Graph g;
    int i,from,to;
    printf("t为1-4,分别表示无向图、有向图、带权无向图、带权有向图\n");
    CreateGraph(&g);//创建图 

    printf("\n输入遍历起点: ");  
    scanf("%d",&i);  
    printf("\n深度优先搜索遍历：");
    DFS(g,i);//深度优先遍历函数 
    printf("NULL\n");

    printf("广度优先搜索遍历："); 
    BFS(g,i);//广度优先遍历函数 
    printf("NULL\n");

    printf("\nDijkstra算法单元最短路径：");
    printf("\n请输入起点和终点（中间用空格）：");
    scanf("%d %d",&from,&to);
    SHORT(&g,from,to);//Dijkstra算法单元最短路径函数    
}

//创建图  
void CreateGraph(Graph *g)  
{
     int i,j,k,w,t;  
     printf("输入顶点数，边数和t（中间用空格）:");  
     scanf("%d %d %d", &(g->numVertexes), &(g->numEdges),&t);  
     printf("\n");  
     for(i=1;i<=g->numVertexes;i++)//通过循环输入顶点信息  
     {  
         getchar();  
         printf("输入第%d顶点信息vexs[%d]=",i,i);  
         scanf("%c",&(g->vexs[i]));  
     }  
     printf("\n");  
     for(i=1;i<=g->numVertexes;i++)  
        for(j=1;j<=g->numVertexes;j++)  
            if (t>2)
                    g->arc[i][j] = INFINITY;//区别是否带权值  
            else
                    g->arc[i][j]=0;   
     for(k=1;k<=g->numEdges;k++)//通过循环输入边的信息  
       {  
        printf("输入有联系的两个顶点（中间用空格）:");  
        scanf("%d %d",&i,&j);  
        if(i>g->numVertexes ||j>g->numVertexes)  
            exit(0);  
        if(t>2)  
        {  
              printf("输入权值:");  
              scanf("%d",&w);  
              g->arc[i][j]=w;  
              if(t==3)  
                g->arc[j][i]=w;  
        }  
        else  
        { 
            g->arc[i][j]=1;  
              if (t==1)
                g->arc[j][i]=1;  
        }  
     }  
     printf("\n");  
     printf("输出邻接矩阵:\n");  
     for(i=1;i<=g->numVertexes ;i++)  
     {  
         for(j=1;j<=g->numVertexes ;j++)  
         {  
             printf("%8d",g->arc[i][j]);  //输出邻接矩阵 
         }  
          printf("\n");  
     }  
}  

//深度优先遍历
void DFS(Graph g,int v)
{
    int j;  
    printf("%d->",v); //输出访问顶点  
    visited[v]=1;//全局数组访问标记置1表示已经访问  
    for(j=1; j<=g.numVertexes; j++)  
           if ((g.arc[v][j]!=0)&&(g.arc[v][j]!=65535)&&(!visited[j]))  
            DFS (g,j);//递归访问非0非无穷顶点 
} 

//广度优先遍历
void BFS(Graph g,int v)
{
    int  q[g.numVertexes+1] ;  
    int  i,f,r,j ;
    for(i=0;i<g.numVertexes;i++)
        visited[i]=0;  //重置访问标记 
    f=r=0 ;  
    printf("%d->",v);//输出第一个顶点  
    visited[v]=1 ;//标记已访问  
    r++;  
    q[r]=v;  
    while (f<r)  
    {
          f++; 
          v=q[f];  
          for (j=1; j<=g.numVertexes; j++) //广度优先遍历依次访问与上一顶点有联系的点 
        {
            if ((g.arc[v][j]!=0)&&(g.arc[v][j]!=65535)&&(!visited[j]))  
            {   
                printf("%d->",j);//输出访问顶点 
                visited[j]=1 ; 
                r++; 
                q[r]=j ;  
            }
        }  
    }  
} 

//单元最短路径算法
void SHORT(Graph *g,int from,int to)
{
    int i,j,index=-1;  
    int n=1;//记录已经求出的两个点之间的最短距离的个数  
    ArrayNode shortestPath[MAXVEX];  
    int flag[MAXVEX]={0};//标记，为1表示到这个顶点的最短距离已求出  

    //1.求from到各个顶点的直接距离，即初始化shortestPath数组  
    for(i=1;i<=g->numVertexes;i++)
    {  
        if(from==i)
        {  
            shortestPath[i].distance=0;  
            shortestPath[i].path[0]=i;  
            flag[from]=1;  
        }  
        else if(g->arc[from][i]>0)
        {  
            shortestPath[i].path[0]=from;  
            shortestPath[i].path[1]=i;  
            shortestPath[i].distance=g->arc[from][i];  
        }
        else 
            shortestPath[i].distance=INFINITY;  
    }

    //2.每次求一个最短路径  
    while(n<=g->numVertexes)
    {  
        //选择shortestPath中距离最小的，求出from到这个顶点的最短路径  
        index=-1;  
        for(i=1;i<=g->numVertexes;i++)
        {  
            if(i==from)  
                continue;  
            if(flag[i]==0 && index==-1 && shortestPath[i].distance!=INFINITY)  
                index=i;  
            if(flag[i]==0 && index!=-1 && shortestPath[i].distance<shortestPath[index].distance)  
                index=i;  
        }  
        flag[index]=1;  
        //修改到各个顶点的最短路径  
        for(i=1;i<=g->numVertexes;i++)
        {  
            if(i==from)  
            continue;  
            if(g->arc[index][i]>0 && g->arc[index][i]+shortestPath[index].distance<shortestPath[i].distance)
            {  
                shortestPath[i].distance=g->arc[index][i]+shortestPath[index].distance;  
                //修改路径  
                j=0;  
                while(1)
                {  
                    shortestPath[i].path[j]=shortestPath[index].path[j];  
                    if(shortestPath[index].path[j]==index)  
                        break;  
                    j++;  
                }  
                shortestPath[i].path[j+1]=i;  
            }  
        }  
        n++;  
    }  

    //输出from到to的最短路径及长度  
    if(shortestPath[to].distance==INFINITY)
    {  
        printf("%d到%d没有路径\n",from,to);  
        return;  
    }  
    printf("%d到%d的最短路径长度是：%d\n",from,to,shortestPath[to].distance);  
    printf("经过的顶点：  ");  
    i=0;  
    while(1)
    {  
        printf("%-3d",shortestPath[to].path[i]);  
        if(shortestPath[to].path[i]==to)  
        break;  
        i++;  
    }  
    printf("\n");
}

4 查找和排序

要求：

(1)任意给定无序序列，用对半检索法，交互检索任意给定的关键字KEY；

(2)任意给定无序序列，用快速排序法对序列进行排序，并统计交换次数；

(3)任意给定无序序列，用冒泡排序法对序列进行排序，并统计交换次数和排序趟数。

程序：

#include "stdio.h"
#define N 6//序列长度(可修改)

//函数声明 
int halfSort(int *b,int n); 
void quickSort(int *b,int l,int r);
void bubbleSort(int *bb,int r);

//全局变量定义 
int o,p,k;
int KEY; //检索的关键字 

//主函数 
int main()
{
    int i,j,q;
    int a[100],aa[100],aaa[100];//以数组方式定义序列 
    printf("Hello World!\n");

    printf("\n1.请输入任意序列(用回车隔开)\n");
    for(i=1;i<=N;i++)
    scanf("%d",&a[i]);//输入无序序列 
    quickSort(a,1,N);//先排序再进行对半检索
    printf("排序后序列为：");
    for(j=1;j<=N;j++)
    printf("%d ",a[j]);//输出有序序列 
    printf("\n请输入需要检索的关键字KEY:"); 
    scanf("%d ",&KEY);
    q=halfSort(a,N);//对半检索函数调用 
    printf("对半检索-关键字位置为：%d\n",q);

    printf("\n2.请输入任意序列(用回车隔开)\n");
    for(i=0;i<N;i++)
    scanf("%d",&aa[i]);//输入无序序列 
    quickSort(aa,0,N-1);//快速排序函数调用 
    printf("快速排序后序列为：");
    for(j=0;j<N;j++)
    printf("%d ",aa[j]);//输出有序序列 
    printf("\n交换次数为：%d\n",k);

    printf("\n3.请输入任意序列(用回车隔开)\n");
    for(i=0;i<N;i++)
    scanf("%d",&aaa[i]);//输入无序序列 
    bubbleSort(aaa,N);
    printf("冒泡排序后序列为：");//冒泡排序函数调用 
    for(j=0;j<N;j++)
    printf("%d ",aaa[j]);//输出有序序列 
    printf("\n交换次数为：%d\n",o);
    printf("排序趟数为：%d\n",p);

    return 0; 
}

//对半检索函数 
int halfSort(int *b,int n)
{
    int high,mid,low;
    int rs=0;
    low=1;high=n;//初始状态 
    while(low<=high)//判断查找是否结束 
    {
        mid=(low+high)/2;
        if(KEY<b[mid]) high=mid-1;//关键字在前半区 
        else
        if(KEY>b[mid]) low=mid+1;//关键字在后半区 
        else {rs=mid;break;}
    }
    return rs;
}

//快速排序函数 
void quickSort(int *bb,int l,int r)
{
   int m,n;
   int temp;
   if(l>=r) return;//只有一个记录或无记录，无须排序 
   m=l;
   n=r;
   temp=bb[m];
   while(m!=n)//寻找temp的最终位置 
   {
           while((bb[n]>=temp)&&(n>m))
           n--;//从右向左扫描，查找第一个小于temp的记录 
           if(m<n)
           {
            bb[m++]=bb[n];k++;
        }
           while((bb[m]<=temp)&&(n>m))
           m++;//从左向右扫描，查找第一个大于temp的记录 
           if(m<n)
           {
            bb[n--]=bb[m];k++;
          }
       }
       bb[m]=temp;//找到temp的最终位置 
       quickSort(bb,l,m-1);//递归处理左区间 
       quickSort(bb,m+1,r);//递归处理右区间 
}    

//冒泡排序函数 
void bubbleSort(int *bbb,int r)
{
    int m,n,noswap;
    int temp;
    for(m=0;m<(r-1);m++)//外循环，做N-1次起泡 
    {
        noswap=1;
        for(n=0;n<(r-m-1);n++)//内循环，置交换标志 
        if(bbb[n+1]<bbb[n])//比较 
        {
            temp=bbb[n];
            bbb[n]=bbb[n+1];
            bbb[n+1]=temp;//交换 
            o++;
            noswap=0;
        }
        if(noswap) break;//本趟起泡未发生记录交换，算法结束 
        p++;
    }
}
文章作者: BoBoRing
文章链接: http://boboring.github.io/2020/03/06/My-Post0-3/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 BoBoRing !
C语言
评论
  目录