数据结构实验

1.有序数组的插入

代码：

bool Insert( List L, ElementType X ){
    //溢出
    if(L->Last==MAXSIZE-1) 
        return false;
    //插入在最后一位
    if(L->Data[L->Last] > X){
        L->Data[L->Last+1]=X;
        L->Last++;
        return true;
    }
    int tp=0;int find=0;int tmp=0;
    for(int i=0;i <= L->Last;i++){
        //判断相等时为false
        if(L->Data[i] == X) return false;
        //当大于时插入，只执行一次
        if(L->Data[i] < X && find==0){
            tp = L->Data[i];
            L->Data[i]=X;
            find=1;
        } 
        //将插入位置后所有数据向后移动一位
        if(find==1){
            tmp=L->Data[i+1];
            L->Data[i+1]=tp;
            tp=tmp;
        }
    }
    L->Last++;
    return true;
}

2.带头结点链栈的操作

代码如下（示例）：

Status Push(LinkList L,ElemType e){
    LNode *node = (struct LNode*)malloc(sizeof(struct LNode));
    node->data = e;
    node->next = L->next;
    L->next = node;
}

Status Pop(LinkList L,ElemType *e){
    *e = L->next->data;
    L->next = L->next->next;
}

3.优美的括号序列

代码：

#include
#include
#include
using namespace std;
int main()
{
    string input;
  
    while (cin >> input)
    {
        stackst;
        bool perfect = true;
        for (auto ch : input)
        {
            if (ch == '(')
            {
                st.push(ch);
            }
            else if (ch == ')')
            {
                if (st.empty())
                {
                    perfect = false;
                    break;
                }
               // else if(st.top()=='(')
               //     st.pop();
                else
                {
                    st.pop();
                  //  perfect = false;
                   // break;
                }
            }
        }
        if (perfect) perfect = st.empty();
        cout << (perfect ? "YES" : "NO") << endl;
     }



    return 0;
}

4.单链表逆转

#下列代码的功能是返回带头结点的单链表L的逆转链表。

List Reverse( List L )
{
    Position Old_head, New_head, Temp;
    New_head = NULL;
    Old_head = L->Next;

    while ( Old_head )  {
        Temp = Old_head->Next;
        
Old_head->Next=New_head
;  
        New_head = Old_head;  
        Old_head = Temp; 
    }
    
L->Next=New_head
;
    return L;
}

5. 分糖果（循环线性表）

#include
#include
bool ping(int* a,int n){
    for(int i=1;i 
 6.表达式转换 
#include
#include
#include
char str[27];
int len;
char stack[27];
int top=0;
int index=0;
 
int IsNum(char c)
{
	if(c>='0'&&c<='9'||c=='.')
	  return 1;
	else 
	  return 0;
} 
 
int compare(char a,char b)
{
	if(b==')')return 1;
	if(a=='('||b=='(')return 0;
	switch(b)
	{
		case '+':
		case '-':
			return 1;
		case '*':
		case '/':
			switch(a){
				case '+':
			    case '-':
			    	return 0;
			    case '*':
			    case '/':
			    	return 1;
			}
	}
}
 
int ZhengFu(char a)
{
	if(a=='+'||a=='-')
	 return 1;
	else 
	 return 0;
}
 
void Mainfun()
{
	int space=0; 
	for(index=0;index 
7. 扩展的先序遍历序列创建二叉树 
 
  
  
#include 
#include 

typedef char ElementType;
typedef struct BiTNode{
    ElementType data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

BiTree CreatBinTree();
void  preorder( BiTree T );

int main()
{
    BiTree T = CreatBinTree();
    preorder(  T );
    return 0;
}
void  preorder( BiTree T )
{
   if(T)
   {
     printf("%c",T->data);
     preorder(T->lchild);
     preorder(T->rchild);
   }
}
BiTree CreatBinTree()
{
   char ch;BiTree T;
   scanf("%c",&ch);
   if(ch=='#') return 
c
;
   T=
(BiTree*)malloc(sizeof(BiTree))
;
   T->data=ch;
   T->lchild=
CreatBinTree()
;
   T->rchild=
CreatBinTree()
;
   return T;
} 
8. 计算二叉树的深度 
 
#include
#include
typedef struct BiNode
{
    char data;
    struct BiNode *lchild, *rchild;
}BiTNode, *BiTree;


void CreateBiTree(BiTree * T)
{
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
        *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

int Depth(BiTree T)
{
    int m, n;
    if (
T==NULL
)
        return 0;
    else
    {
        m = 
Depth(T->lchild)
;
        n = 
Depth(T->rchild)
;
        if (m > n)
            return(m + 1);
        else
            return (n + 1);
    }
}

int main()
{
    BiTree tree = NULL;
    CreateBiTree(&tree);
    int depth = Depth(tree);
    printf("%d", depth);
    return 0;
} 
9. 是不是二叉树？ 
int arr[1000001];
int isTree(TreeNode Head){
    memset(arr,0,sizeof(arr));
    return dfs(Head);
}

int dfs(TreeNode root){
    if(root == NULL){
        return 1;
    }
    if(arr[root->data]){
        return 0;
    }
    arr[root->data] = 1;
    return dfs(root->lchild) && dfs(root->rchild);
} 
10. 二叉排序树查找操作 
BSTree SearchBST(BSTree T,ElemType e){
    if(!T||T->data == e)
        return T;
    else if(edata)
        return SearchBST(T->lchild,e);
    else
        return SearchBST(T->rchild,e);
} 
哈夫曼编码  
#include
void f(int *a,int n){
    for(int i=n-1;i>0;i--){
        for(int j=0;j 
  新浪微博热门话题 
#include 
#include 
#include 

#define MAXLENGTH   1000000 // 散列表大小，要保证装填因子小于一定阈值，否则会因频繁的哈希冲突而超时

typedef struct Node
{
    char *topic;            // 话题
    int count;              // 当前话题被提及的次数
    int last;               // 最后一次提及该话题的微博下标（用于去重）
}*Node;

Node hashTable[MAXLENGTH];  // 散列表
Node indices[MAXLENGTH];    // 将散列表紧凑化
int sumOfTopics;            // 话题总数

void solution();
void handle(char *text, int numberOfWeibo);     // 从文本中查找话题
void normalize(char *topic, int numberOfWeibo); // 将话题形式规范化
int hash(char *topic);                          // 计算散列值（可能越界）
int mod(int n);                                 // 对散列值取余
void insert(char *topic, int numberOfWeibo);    // 将话题插入到散列表

int main()
{
    solution();
    return 0;
}

void solution()
{
    int n;
    scanf("%dn", &n);
    char buf[141];
    for (int i = 0; i < n; i++)
    {
        gets(buf);
        handle(buf, i);
    }
    Node maxTitle = indices[0];
    int num = 0;
    for (int i = 1; i < sumOfTopics; i++)
    {
        if (indices[i]->count > maxTitle->count)
        {
            maxTitle = indices[i];
            num = 0;
        }
        else if (indices[i]->count == maxTitle->count)
        {
            if (strcmp(indices[i]->topic, maxTitle->topic) < 0)
            {
                maxTitle = indices[i];
            }
            num++;
        }
    }
    if (maxTitle->topic[0] >= 'a' && maxTitle->topic[0] <= 'z') maxTitle->topic[0] -= 32;
    printf("%sn%dn", maxTitle->topic, maxTitle->count);
    if (num)
    {
        printf("And %d more ...n", num);
    }
}

void handle(char *text, int numberOfWeibo)
{
    char *first;
    char *second;
    char buf[141];
    while ((first = strchr(text, '#')) != NULL && (second = strchr(first + 1, '#')) != NULL)
    {
        strncpy(buf, first + 1, second - first - 1);
        buf[second - first - 1] = '';
        normalize(buf, numberOfWeibo);
        text = second + 1;
    }
}

void normalize(char *topic, int numberOfWeibo)
{
    char *text = topic;
    if (!text || !*text) return;
    // 将非字母、数字的字符替换为空格
    while (*text)
    {
        if (*text >= 'A' && *text <= 'Z') *text += 32;
        else if (!(*text >= 'a' && *text <= 'z') && !(*text >= '0' && *text <= '9')) *text = ' ';
        text++;
    }

    char *first = NULL;
    char *second = NULL;
    char *rear = topic + strlen(topic);
    // 头部去空格
    text = topic;
    while (*text == ' ') text++;
    memmove(topic, text, rear - text + 1);
    rear -= text - topic;
    text = topic;
    // 中间和尾部去空格
    for (; *text; text++)
    {
        if (*text == ' ')
        {
            first = second = text;
            while (*second == ' ') second++;
            if (second - first != 1 && second != rear)
            {
                memmove(first + 1, second, rear - second + 1);
                rear -= second - first - 1;
            }
            else if(second == rear)
            {
                *first = '';
            }
        }
    }
    // 将话题插入散列表中
    insert(topic, numberOfWeibo);
}

int hash(char *topic)
{
    unsigned n = 0;
    while (*topic)
    {
        n += *topic - 'a';
        n <<= 5;
        topic++;
    }
    return n;
}

int mod(int n)
{
    while (n < 0) n += MAXLENGTH;
    return n % MAXLENGTH;
}

void insert(char *topic, int numberOfWeibo)
{
    int key = hash(topic);
    int i = 0;
    int j = 0;
    // 从中间往两侧探测，处理哈希冲突，找空位
    for (; i < MAXLENGTH / 2; i++)
    {
        j = mod(key + i); // 往右侧查找
        if (hashTable[j])
        {
            if (!strcmp(topic, hashTable[j]->topic))
            {
                if (hashTable[j]->last == numberOfWeibo) return;
                ++hashTable[j]->count;
                hashTable[j]->last = numberOfWeibo;
            }
        }
        else break;
        j = mod(key - i); // 往左侧查找
        if (hashTable[j])
        {
            if (!strcmp(topic, hashTable[j]->topic))
            {
                if (hashTable[j]->last == numberOfWeibo) return;
                ++hashTable[j]->count;
                hashTable[j]->last = numberOfWeibo;
            }
        }
        else break;
    }
    // 找到空位后，将新的结点插入到散列表中
    hashTable[j] = (Node)malloc(sizeof(struct Node));
    hashTable[j]->topic = (char*)malloc(strlen(topic) + 1);
    strcpy(hashTable[j]->topic, topic);
    hashTable[j]->count = 1;
    hashTable[j]->last = numberOfWeibo;
    indices[sumOfTopics++] = hashTable[j];
}
 
 那就别担心了 
  
#include
int vis[502], path[502],vec[502][502];
int n, m, cnt, a, b;
int DFS(int x) {
    vis[x] = 1;
    if(path[x]) return path[x];
    for(int i=1;i<=n;i++)
        if(vec[x][i])
            path[x] += DFS(i);
    return path[x];
}
int main(){
    int i;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++) {
        scanf("%d %d",&a,&b);
        vec[a][b]=1;
    }
    scanf("%d %d",&a,&b);
    path[b] = 1;
    cnt = DFS(a);
    int flag = 1;
    for(i=1;i<=n;i++) {
        if(vis[i] && !path[i]) {
            flag = 0;
            break;
        }
    }
    printf("%d ",cnt);
    if(!flag)
        printf("Non");
    else
        printf("Yesn");
    return 0;
}
 
 地下迷宫探索 
#include
#include

#define INFINITY 100000
#define MAXN 1000

typedef int Vertex;
typedef int WeightType;
typedef int DataType;

typedef struct GNode *PtrToGNode;
typedef PtrToGNode MGraph;
struct GNode
{
    int Nv;
    int Ne;
    WeightType **G;
};

typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
struct ENode
{
    Vertex V1, V2;
    WeightType W;
};

MGraph CreateGraph(int VertexNum)
{
    int i,j;
    MGraph Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->G = (WeightType **)malloc(Graph->Nv*sizeof(WeightType *));
    for(i=0; iNv; i++)
    {
        Graph->G[i] = (WeightType*)malloc(Graph->Nv*sizeof(WeightType));
    }

    for(i=0; iNv; i++)
    {
        for(j=0; jNv; j++)
            Graph->G[i][j] = INFINITY;
    }

    return Graph;
}

void InsertEdge(MGraph Graph, Edge E)
{
    Graph->G[E->V1][E->V2] = E->W;
    Graph->G[E->V2][E->V1] = E->W;
}

MGraph BuildGraph(int N, int M)
{
    int i;

    MGraph Graph = CreateGraph(N);
    Graph->Ne = M;

    if(Graph->Ne != 0)
    {
        Edge E = (Edge)malloc(sizeof(struct ENode));
        for(i=0; iNe; i++)
        {
            scanf("%d %d", &E->V1, &E->V2);
            E->V1--;
            E->V2--;
            E->W = 1;
            InsertEdge(Graph, E);
        }
    }

    return Graph;

}

void Visit(Vertex V)
{
    printf("%d ", V+1);
}

int *Visited;
int SP; //start point. set the global variable to satisfy the output format

void DFS(MGraph Graph, Vertex V, void(*Visit)(Vertex))
{
    Visit(V);
    Visited[V] = 1;
    int i;
    for(i=0; iNv; i++)
    {
        if(Graph->G[V][i] == 1 && Visited[i] == 0)     //V is adjacent to i, and i is not visited
        {
            DFS(Graph, i, Visit);
            if(V==SP)
                printf("%d", SP+1);
            else
                Visit(V);
        }
    }
}

int main()
{

    int i,N,M;

    scanf("%d %d %d", &N, &M, &SP);
    SP = SP-1;

    MGraph Graph = BuildGraph(N, M);

    Visited = (int *)malloc(Graph->Nv*sizeof(int));
    for(i=0; iNv; i++)
        Visited[i] = 0;


    DFS(Graph, SP, Visit);
    int flag = 1;
    for(i=0; iNv; i++)
    {
        if(Visited[i] == 0)
        {
            flag = 0;
            break;
        }

    }
    if(flag == 0)
        printf(" %d", 0);

    return 0;
}


 
 深入虎穴 
#include
#include
#include
using namespace std;
vectors[100010];
int track[100010]={0};//这个数组用来标记有前驱的点
int index=0;
void find(int root)//层序搜索函数，搜到不能再往下搜就算找到了最远的门
{
 queueq;//建立一个队列
    q.push(root);//把根节点加入队列
    while(!q.empty())//这就开始时循环着往下遍历了
    {
        int now = q.front();
        q.pop();
        index=now;
        for(int i=0;i 
 公路村村通 
#include
#include
int map[1001][1001];
int minCost[1001];//记录与该顶点邻接的边最小权值 
int visited[1001];
int N,M;
int min(int a,int b)
{
	return a > b ? b : a;
}
int prime()
{
	int i,sum=0,v;
	for(i=1;i<=N;i++) 
		minCost[i]=99999999;//初始化为最大
	minCost[1]=0;
	while(1)
	{
		v = -1;
		for(i=1;i<=N;i++)//找到权值最小的边所对应的顶点
		{
			if(!visited[i]&&(v==-1||minCost[v]>minCost[i]))
				v = i;
		}
		if(v==-1)
			break;//说明顶点都已经经过了
		if(minCost[v]==99999999)
			return 0;//如果有个孤立顶点，最小权值不会变，可以判断图是否连通		
		visited[v]=1;
		sum+=minCost[v];
		for(i=1;i<=N;i++)
		{
			if(map[v][i])
				minCost[i]=min(minCost[i],map[v][i]);//每次更新与顶点邻接的边的最小权值
		}
	}
	for(i=1;i<=N;i++)
	{
		if(!visited[i])
			return 0;
	}
	return sum;
} 
int main()
{
	int i;
	int city1,city2,cost;
	scanf("%d %d",&N,&M);
	for(i=0;i 
 选择排序 
#include
int main()
{
	int n,i=0,min,index,k,h,flag=0;;
	scanf("%d",&n);
	int a[n];
	for(i=0;ia[k])
			{
				min=a[k];
				index = k;
				flag=1;
			}
		}
		if(flag==1)
		{
			a[index] = a[i];
			a[i] = min;
		}
		flag=0;
		printf("step %d: ",i+1);
		for(h=0;h 
 寻找大富翁 
#include
int main(){
	long long n,i,j,index;
	int m,t,count=0;
	int a[1000000];
	scanf("%lld%d",&n,&m);
	for(i=0;i

数据结构实验

C/C++/C#相关栏目本月热门文章