[数据结构与算法]数据结构实验题

实验一

#include <stdio.h>

#define N 100000

int head,e[N],ne[N],idx;

void init(){
    head=-1;
    idx=0;
}

//给头节点插入元素
void add_head(int x){
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}

//添加元素在k的位置
void add(int k,int x){
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}

//替换制定位置元素
void insert(int k,int x){
    e[k]=x;
}

//删除第k个元素
void delete(int k){
    ne[k]=ne[ne[k]];
}

//检索第k个元素
void find(int k){
    for(int i=head;i!=-1;i=ne[i])
    //for(int i=0;i<idx;++i)
        if(i==k)
            printf("%d\n",e[k]);
}

//打印链表
void printf_list(){
    printf("现在链表元素为:\n");
    for(int i=head;i!=-1;i=ne[i]) printf("%d ",e[i]);
    puts("");
}

//表长
void size_list(){
    printf("%d\n",idx);
}

void show()
{
	printf("----------------------------- \n");
	printf("输入1: 修改指定位置元素\t");
	printf("输入2: 删除指定位置元素\t");
	printf("输入3: 指定位置插入新元素\t");
	printf("输入4: 打印输出链表\n");
	printf("输入5: 查找指定位置元素\t");
	printf("输入6: 输出链表长度\t");
	printf("输入0: 退出程序\t");
	printf("----------------------------- \n");
}

int main(){
    show();

    init();
    while(1){
        int k,x,p;
        printf("请输入你要操作的数字：");
        scanf("%d",&p);
        if(p==0)
            break;
        else if(p==1){
            printf("请输入你要替换的元素下标及替换后的元素:");
            scanf("%d %d",&k,&x);
            insert(k-1,x);
        }
        else if(p==2){
            printf("请输入你要删除的元素:");
            scanf("%d",&k);
            if(k==0) head=ne[head];
            else delete(k-2);
            idx--;
        }
        else if(p==3){
            printf("输入你要插入元素的下标及元素：");
            scanf("%d %d",&k,&x);
            if(idx==0)
                add_head(x);
            else add(k-2,x);
        }
        else if(p==4){
            printf_list();
        }
        else if(p==5){
            printf("请输入你要检索元素的下标");
            scanf("%d",&k);
            find(k-1);
        }
        else if(p==6){
            size_list();
        }
        printf_list();

    }
    return 0;
}

实验四

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

typedef char elemType;

typedef struct BiTNode {
    elemType data;
    struct BiTNode *lchild, *rchild;
    int LTag, RTag;
} BiThreadNode, *BiThreadTree;    

BiThreadNode *pre; 



void visit(elemType x) // 输出元素x
{ 
    printf("%c ", x); 
}

BiThreadTree createBiThreadTree()   // 先序输入节点的值，构造二叉树
{
    BiThreadNode *T;
    char ch;

    if ((ch = getchar()) == '#')
        T = NULL;
    else {
        T = (BiThreadNode *)malloc(sizeof(BiThreadNode));
        T->data = ch;
        T->lchild = createBiThreadTree();
        T->rchild = createBiThreadTree();
    }

    return T;
}

void InThreading(BiThreadTree T)    // 创建中序线索二叉树
{
    if (T != NULL) {
        InThreading(T->lchild); 
        if (T->lchild == NULL) {
            T->LTag = 1;
            T->lchild = pre;
        }
        else
            T->LTag = 0;
        if (pre->rchild == NULL) {
            pre->RTag = 1;
            pre->rchild = T;
        }
        else
            pre->RTag = 0;

        pre = T;
        InThreading(T->rchild); 
    }
}

BiThreadNode *CreateInThrTree(BiThreadTree T)   // 中序遍历线索化
{
    BiThreadNode *ThrHead;
    ThrHead = (BiThreadNode *)malloc(sizeof(BiThreadNode));
    ThrHead->RTag = 1;
    ThrHead->rchild = ThrHead; 
    ThrHead->LTag = 0;
    if (T == NULL)
        ThrHead->lchild = ThrHead; 
    else {
        ThrHead->lchild = T;
        pre = ThrHead; 
        InThreading(T);        
        pre->rchild = ThrHead;
        pre->RTag = 1;
        ThrHead->rchild = pre; 
    }
    return ThrHead;
}

void ThrInOrderTraverse(BiThreadTree ThrHead)   // 遍历中序线索二叉树
{
    BiThreadNode *temp = ThrHead->lchild; 
    while (temp != ThrHead) {
        while (temp->LTag == 0)
            temp = temp->lchild; 
        visit(temp->data);
        while (temp->RTag == 1 && temp->rchild != ThrHead) {
            temp = temp->rchild;
            visit(temp->data);
        }
        temp = temp->rchild; 
    }
}

int main()
{
    BiThreadTree root;

    printf("请按先序顺序输入节点值，输入‘#’代表节点为空：\n");
    root = createBiThreadTree();
    BiThreadNode *ThrHead = CreateInThrTree(root);
    printf("中序为：\n");
    ThrInOrderTraverse(ThrHead);
    puts("");
    return 0;
}

实验七

#include <stdio.h>
#include <string.h>

typedef int bool;
#define N 100010

int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];

void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

bool topsort(){
    int hh=0,tt=-1;
    for(int i=1;i<=n;++i){
        if(!d[i])
        q[++tt]=i;
    }
    
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(--d[j]==0)
            q[++tt]=j;
        }
    }
    return tt==n-1;

}

int main(){
    printf("请输入结点数目：N=\n");
    scanf("%d",&n);
    printf("请输入有向图的关联对数E=\n");
    scanf("%d",&m);
    memset(h,-1,sizeof h);
    for(int i=0;i<m;++i){
        int a,b;
        printf("输入第%d对关联对<j,k>\n",i+1);
        scanf("%d%d",&a,&b);
        add(a,b);
        d[b]++;
    }
    
    if(!topsort()) puts("有环，不能进行拓扑排序！\n");
    else {
        printf("拓扑排序为：\n");
        for(int i=0;i<n;++i) printf("%d ",q[i]);
        puts("");
    }
   
    return 0;
}

• 刚做出来，不要作死测边缘数据

• 给想自己做的同学提供思路(也可能是死路)

• 编译环境：gcc 9.3.0