数据结构算法，王道练习题求解(语言-c语言)

题目：某递增有序顺序表，设计算法，查找表中值为x的元素。若找到，将其与后继元素交换位置；若找不到，将其插入并保持表仍然是递增有序的！
问题：其他都解决了，为什么再怎么修改，插入的x元素总是在目标位置后一个位置呢？请各位在我的算法上修改，刚学这门课，不太懂什么高深的算法，万分感谢！

#include<stdlib.h>
#include<stdio.h>
# define Maxsize 100
# define ElemType int
# define Status int
//结构
typedef struct {
    ElemType* elem;
    int length;
    int listsize;
}SqList;
//初始化
Status InitList(SqList& L)
{
    L.elem = (ElemType*)malloc(Maxsize * sizeof(ElemType));
    if (!L.elem) return false;
    L.length = 0;
    L.listsize = Maxsize;
    return true;
}
//输入数据
Status Enter(SqList& L, int n)
{
    for (int i = 0; i < n; i++)
    {
        scanf_s("%d", &(L.elem[i]));
        L.length++;
    }
    return true;
}
//输出数据
Status Out(SqList& L)
{
    if (!L.elem)
        return false;
    for (int i = 0; i < L.length; i++)
        printf("%d ", L.elem[i]);
    return true;
}
Status Handle(SqList& L,int x)
{
    int t, m;
    for (int i = 0; i < L.length; i++)
    {
        if (x == L.elem[i])
        {
            if (i < L.length - 1)
            {
                t = L.elem[i];
                L.elem[i] = L.elem[i + 1];
                L.elem[i + 1] = t;
            }
            if (i = L.length - 1)
            {
                return false;
            }
        }
        else
        {
            if (x < L.elem[0])
            {
                int* q = &(L.elem[0]);
                for (int* p = &(L.elem[L.length - 1]); p >= q; --p)
                    *(p + 1) = *p;
                *q = x;
                ++L.length;
            }

            if (x > L.elem[i] && x < L.elem[i + 1])
            {
                int* q = &(L.elem[i+1]);
                for (int* p = &(L.elem[L.length-1]); p >= q; --p)
                    *(p + 1) = *p;
                *q = x;
                ++L.length;
            }
            if (x > L.elem[L.length - 1])
            {
                int* q = &(L.elem[L.length]);
                for (int* p = &(L.elem[L.length - 1]); p >= q; --p)
                    *(p + 1) = *p;
                *q = x;
                ++L.length;
            }
        }
    }
    return true;

            
}


int main()
{
    SqList L;
    InitList(L);
    int x, n;
    printf("输入表的元素规模：");
    scanf_s("%d", &n);
    printf("请输入表：");
    Enter(L, n);
    printf("请输入x的值以完成操作：");
    scanf_s("%d", &x);

    printf("操作之前的表为：");
    Out(L);

    Handle(L, x);
    printf("\n操作之后的表为：");
    Out(L);
    return 0;
}
![img](https://img-mid.csdnimg.cn/release/static/image/mid/ask/065189346386190.png "#left")

这个链接里面的SList.c里面有一个在pos位置前插入，你可以看看，入口：https://gitee.com/xiaobai-is-working-hard-jy/c-language-jy/blob/master/SList/SList/SList.c，

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7660439
• 这篇博客你也可以参考下：c语言实现赫夫曼树的构建以及生成赫夫曼编码（《数据结构》算法6.12）
• 除此之外, 这篇博客: 哈夫曼树的C语言详解中的 如果介于两个结点权重值之间，替换原来较大的结点； 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

#include<iostream>
#include<string.h>
#define  MAX 10000 
/*
请输入一段文字:this*program*is*my*favourite
字符和权值信息如下
字符：t  权值：2
字符：h  权值：1
字符：i  权值：3
字符：s  权值：2
字符：*  权值：4
字符：p  权值：1
字符：r  权值：3
字符：o  权值：2
字符：g  权值：1
字符：a  权值：2
字符：m  权值：2
字符：y  权值：1
字符：f  权值：1
字符：v  权值：1
字符：u  权值：1
字符：e  权值：1
********************************
字符编码为：
t:1000
h:11010
i:001
s:1001
*:011
p:11011
r:010
o:1010
g:11100
a:1011
m:1100
y:11101
f:11110
v:11111
u:0000
e:0001
文字编码为：
100011010001100101111011010101011100010101111000110011001011110011101011111101011111111010000001000110000001
********************************
译码：
请输入要译码的二进制字符串,输入'#'结束：100011010001100101111011010101011100010101111000110011001011110011101011111101011111111010000001000110000001#
译码为:
this*program*is*my*favourite
是否继续?(Y/N):
*/
using namespace std;
typedef struct {
	char letter, *code;
	int weight;
	int parent, lchild, rchild;
}HTNode, *HuffmanTree;
int n;
char coding[100];
int Min(HuffmanTree &HT, int i)
{
	int j;
	unsigned int k = MAX;
	int flag;
	for (j = 0; j <= i; ++j)
	{
		if (HT[j].weight < k && HT[j].parent == 0)//用父结点是否为0来判断此结点是否已经被选过  
		{
			k = HT[j].weight;
			flag = j;
		}
	}
	HT[flag].parent = 1;//作个标记，说明已经被选择了，因为在Select函数中要选择权值小的两个结点  
	return flag;
}
void Select(HuffmanTree &HT, int i, int &s1, int &s2)
{
	//在HT[1...i]中选择parent为0且权值最小的两个结点，其序号分别为s1,s2  
	//s1 <= s2  
	s1 = Min(HT, i);
	s2 = Min(HT, i);
}
void CreateHuffmanTree(HuffmanTree &HT, char t[], int w[])
{
	int m;
	int i, s1, s2;
	if (n <= 1)
		return;
	m = 2 * n - 1; //总共需要2n－1个节点
	HT = new HTNode[m + 1];//开辟空间
	for (i = 0; i<n; i++)
	{
		HT[i].code = '\0';
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
		HT[i].letter = t[i];
		HT[i].weight = w[i];
	}
	for (i = n; i <= m; i++)
	{
		HT[i].code = '\0';
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
		HT[i].letter = ' ';
		HT[i].weight = 0;
	}
	cout << "********************************" << endl;
	for (i = n; i<m; i++)
	{
		Select(HT, i - 1, s1, s2);//在n个数中找出权值最小的两个

		HT[s1].parent = i;
		HT[s2].parent = i;//将他们两个的parent节点设置为i;

		HT[i].lchild = s1;
		HT[i].rchild = s2;//把这两个分别当作左右节点
		HT[i].weight = HT[s1].weight + HT[s2].weight;//他们两个的双亲为他们两个的和；

	}
}
void CreatHuffmanCode(HuffmanTree HT)
{
	int start, c, f;
	int i;
	char *cd = new char[n];
	cd[n - 1] = '\0';
	cout << "字符编码为：" << endl;
	for (i = 0; i<n; i++)
	{
		start = n - 1;
		c = i;
		f = HT[i].parent;
		while (f != 0){
			--start;
			if (HT[f].lchild == c){
				cd[start] = '0';
			}
			else{
				cd[start] = '1';
			}
			c = f;
			f = HT[f].parent;
		}
		HT[i].code = new char[n - start];
		strcpy(HT[i].code, &cd[start]);
		cout << HT[i].letter << ":" << HT[i].code << endl;
	}
	delete cd;
}
void HuffmanTreeYima(HuffmanTree HT, char cod[], int b)           //译码
{
	char sen[100];
	char temp[50];
	char voidstr[] = " ";       //空白字符串
	int t = 0;
	int s = 0;
	int count = 0;
	for (int i = 0; i<b; i++)
	{
		temp[t++] = cod[i];     //读取字符
		temp[t] = '\0';        //有效字符串
		for (int j = 0; j<n; j++){        //依次与所有字符编码开始匹配
			if (!strcmp(HT[j].code, temp)){                //匹配成功
				sen[s] = HT[j].letter;    //将字符保存到sen中
				s++;
				count += t;
				strcpy(temp, voidstr);                //将TEMP置空 
				t = 0;          //t置空
				break;
			}
		}
	}
	if (t == 0){     //t如果被置空了，表示都匹配出来了，打印译码
		sen[s] = '\0';
		cout << "译码为:" << endl;
		cout << sen << endl;
	}
	else{                             //t如果没有被置空 ， 源码无法被完全匹配
		cout << "二进制源码有错！从第" << count + 1 << "位开始" << endl;
	}
}
int main()
{
	HuffmanTree HT;
	char a[100], buff[1024], p;//a为存放字符 buff为输入的字符串 p为输入译码时的字符 
	int b[100];//存放权值信息 
	int i, j;
	int symbol = 1, x, k; //译码时做判断用的变量  
	cout << "请输入一段文字:";
	cin >> buff;
	int len = strlen(buff);
	for (i = 0; i<len; i++)
	{
		for (j = 0; j<n; j++)
		{
			if (a[j] == buff[i])
			{
				b[j] = b[j] + 1;
				break;
			}
		}
		if (j >= n)
		{
			a[n] = buff[i];
			b[n] = 1;
			n++;
		}
	}
	cout << "字符和权值信息如下" << endl;
	for (i = 0; i<n; i++)
	{
		cout << "字符：" << a[i] << "  权值：" << b[i] << endl;
	}
	CreateHuffmanTree(HT, a, b);
	CreatHuffmanCode(HT);
	cout << "文字编码为：\n";
	for (int i = 0; i < len; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (buff[i] == HT[j].letter)
			{
				cout << HT[j].code;
				break;
			}
		}
	}
	cout <<endl<< "********************************" << endl;
	cout << "译码：" << endl;
	while (1)
	{
		cout << "请输入要译码的二进制字符串,输入'#'结束：";
		x = 1;//判断是否有非法字符只能是0 1 
		k = 0;//作为循环变量来使coding【k】=输入的字符 
		symbol = 1;//判断是否输入结束 
		while (symbol){
			cin >> p;
			if (p != '1'&&p != '0'&&p != '#'){ //若存在其它字符，x设为0，表示输入的不是二进制
				x = 0;
			}
			coding[k] = p;
			if (p == '#')
				symbol = 0;  //#号结束标志
			k++;
		}
		if (x == 1){
			HuffmanTreeYima(HT, coding, k - 1);        //进行译码
		}
		else{
			cout << "有非法字符！" << endl;
		}
		cout << "是否继续?(Y/N):";
		cin >> p;
		if (p == 'y' || p == 'Y')
			continue;
		else
			break;
	}
	return 0;
}

 

• 您还可以看一下 朱有鹏老师的宏定义与预处理、函数和函数库-C语言专题第6部分课程中的 4.6.2.C语言预处理代码实战小节, 巩固相关知识点
  
• 以下回答来自chatgpt:

  针对优化这个问题，我会给出以下建议：

  1.推荐学习资源：

  • 《算法（第四版）》- Robert Sedgewick 和 Kevin Wayne，其中有一个章节是关于二叉树相关算法的，涵盖了基本结构和常规操作等。
  • 《数据结构》- 严蔚敏，该书内容质量非常高，关于二叉树的实现和应用有很详细的介绍。
  • 在线网站《LeetCode》- 可以练习二叉树问题，在实践中加深对于二叉树的理解。

  2.实现二叉树需要注意的问题：

  • 二叉树的每个节点都包含左孩子、右孩子和数据，因此在定义结点时需要注意定义结构体，结构体中包含左孩子、右孩子和数据。
  • 在二叉树的实现中，可能需要用到栈和队列等数据结构来实现深度遍历和广度遍历，因此需要注意如何定义和使用栈和队列。
  • 在实现二叉树算法时需要注意根据具体的需求选择遍历方式，并根据需要进行遍历来实现查找或者其他操作。
  • 需要注意二叉树的常规操作，例如插入、删除、查找等操作，在操作时需要注意二叉树特有的性质，例如左子树小于父节点，右子树大于父节点。

  3.具体的实现代码：

  // 定义结点
  typedef struct TNode{
      int data;
      struct TNode *lchild, *rchild;
  }TNode, *BiTree;
  
  // 定义队列，实现层序遍历
  typedef struct queen_node{
      TNode *nodes[100];
      int front;
      int size;
      int rear;
  }queen_node, *Queen;
  
  // 定义栈结构
  typedef struct stack_node{
      TNode *nodes[100];
      int top;
      int size;
  }*Stack;
  
  //初始化栈
  Stack init_Stack(){
      Stack stack = (Stack)malloc(sizeof(stack_node));
      stack->top = -1;
      stack->size = 100;
      return stack;
  }
  
  // 入栈操作
  void push_stack(Stack S, TNode* p){
      if (S->top<S->size) {
          S->nodes[++S->top] = p;
      }
  }
  
  // 出栈操作
  TNode* pop_stack(Stack s){
      if (s->top!=-1) {
          return s->nodes[s->top--];
      }
      return NULL;
  }
  
  // 初始化队列
  Queen init_queen(){
      Queen q = (Queen)malloc(sizeof(queen_node));
      q->front= -1; 
      q->rear = -1; 
      q->size = 100;
      return q;
  }
  
  //入队操作
  void in_queen(Queen q, TNode* m){ 
      int a = (q->rear+1)%q->size;
      if (a != q->front){
           q->nodes[(++q->rear) % q->size] = m;
      }
  }
  
  //出队
  TNode* out_queen(Queen q){
      if (q->front!=q->rear) {
        return q->nodes[(++q->front)%q->size];
      } else {
          return NULL;
      }
  }
  
  // 实现树的遍历
  void PreOrder(BiTree root) {
      Stack S = init_Stack(); // 初始化栈
      TNode* p = root;
      while(p!=NULL || S->top!=-1){
          while(p!=NULL){
              printf("%d", p->data);
              push_stack(S, p);
              p = p->lchild;
          }
          if (S->top!=-1) {
              p = pop_stack(S);
              p = p->rchild;
          }
      }
  }
  
  // 实现树的广度优先遍历
  void BFS(BiTree root) {
      Queen Q = init_queen(); // 初始化队列
      TNode* p = root;
      in_queen(Q, p);
      while(Q->front != Q->rear) {
          p = out_queen(Q);
          printf("%d",p->data);
          if (p->lchild) in_queen(Q, p->lchild);
          if (p->rchild) in_queen(Q, p->rchild);
      }
  }
  

  以上是我对于这个问题的解答，如果有任何问题，请随时向我咨询。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

修改如下，改动处见注释，供参考：

#include<stdlib.h>
#include<stdio.h>
# define Maxsize 100
# define ElemType int
# define Status int
//结构
typedef struct {
    ElemType* elem;
    int length;
    int listsize;
}SqList;
//初始化
Status InitList(SqList& L)
{
    L.elem = (ElemType*)malloc(Maxsize * sizeof(ElemType));
    if (!L.elem) return false;
    L.length = 0;
    L.listsize = Maxsize;
    return true;
}
//输入数据
Status Enter(SqList& L, int n)
{
    for (int i = 0; i < n; i++)
    {
        scanf_s("%d", &(L.elem[i]));
        L.length++;
    }
    return true;
}
//输出数据
Status Out(SqList& L)
{
    if (!L.elem)
        return false;
    for (int i = 0; i < L.length; i++)
        printf("%d ", L.elem[i]);
    return true;
}
Status Handle(SqList& L, int x)
{
    int t, m;
    for (int i = 0; i < L.length; i++)
    {
        if (x == L.elem[i])
        {
            if (i < L.length - 1)
            {
                t = L.elem[i];
                L.elem[i] = L.elem[i + 1];
                L.elem[i + 1] = t;
            }
                       //if (i = L.length - 1) 修改
                       //{                     修改
            return true; //return false;       修改
                       //}                     修改
        }
    }  //   修改
    for (int i = 0; i < L.length; i++)    //else 修改
    {
            if (x < L.elem[0])
            {
                int* q = &(L.elem[0]);
                for (int* p = &(L.elem[L.length - 1]); p >= q; --p)
                    *(p + 1) = *p;
                *q = x;
                ++L.length;
            }

            else if (x > L.elem[i] && x < L.elem[i + 1])  // 修改
            {
                int* q = &(L.elem[i + 1]);
                for (int* p = &(L.elem[L.length - 1]); p >= q; --p)
                    *(p + 1) = *p;
                *q = x;
                ++L.length;
            }
            else if (x > L.elem[L.length - 1])      //  修改
            {
                int* q = &(L.elem[L.length]);
                for (int* p = &(L.elem[L.length - 1]); p >= q; --p)
                    *(p + 1) = *p;
                *q = x;
                ++L.length;
            }
    }
    return true;
}
int main()
{
    SqList L;
    InitList(L);
    int x, n;
    printf("输入表的元素规模：");
    scanf_s("%d", &n);
    printf("请输入表：");
    Enter(L, n);
    printf("请输入x的值以完成操作：");
    scanf_s("%d", &x);

    printf("操作之前的表为：");
    Out(L);

    Handle(L, x);
    printf("\n操作之后的表为：");
    Out(L);
    return 0;
}