空安

用户名：KongAn

访问量：5858

签　名：

等　　级
排　　名	3428
经　　验	1932
参赛次数	0
文章发表	27
年　　龄	0
在职情况	学生
学　　校	哈尔滨商业大学
专　　业

　　自我简介：

TA的其他文章

DNA-题解(C语言代码)
浏览：305

IP判断-题解(C语言代码)
浏览：130

K-进制数-题解(C++代码)
浏览：196

你可能喜欢

A+B for Input-Output Practice (I) （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C++代码）

空安---《数据结构》第二章之上

　　作者: 空安　　　　发表时间：2020-04-22 23:52:53 浏览：192　|　评论：0　

先对第一章做几个补充：
1、抽象数据类型（ADT）= 数据的逻辑结构 + 数据运算 
2、输出型参数:star:
```cpp
返回值 函数名（输入参数，输出参数）//输出参数要用引用型参数
{
	//实现代码
}
```
由此便能够理解上一章的例题：求一元二次方程的解的代码
代码如下：
```cpp
int solution(float a,float b,float c,float &x1,float &x2)
{
    float d,x1,x2;  //这里必须去掉x1,x2 否则会报错  我猜测原因是x1和x2已经定义过了 重复定义容易造成程序紊乱
    d=b*b-4*a*c;
    if(d>0)
    {
        x1=(-b+sqrt(d))/(2*a);
        x2=(-b-sqrt(d))/(2*a);
        return 2;
    }
    else if(d==0)
    {
        x1=x2=(-b)/(2*a);
        return 1;
    }
    else
        return 0;
}
```

但是疑惑的是 我该如何在主函数里调用这个函数 并输出解的个数以及每个解的值
（存疑，明天问老师）
补充上述代码：
```cpp
int main()
{
    float a,b,c,x1,x2;
    cin>>a>>b>>c;
    cout<<solution(a,b,c,x1,x2)<<endl;
    if(solution(a,b,c,x1,x2))
        cout<<x1<<" "<<x2<<endl;
}
```

接下来才是第二章内容
### 2.1线性表的基本概念
**2.1.1线性表的基本概念**

1、线性表是一个具有**相同性质**的数据元素的**有限序列**
2、逻辑表示：（a1，a2，……，ai，ai+1，……，an）

**2.1.2线性表的运算**
（1）初始化线性表InitList(&L)
（2）销毁线性表DestroyList（&L）
（3）判断线性表是否为空表ListEmpty(L)
（4）求线性表的长度ListLength（L）
（5）输出线性表DispList(L)
（6）求线性表L中指定位置的某个数据元素GetElem（L，i，&e）
（7）定位查找LocateElem（L，e）
（8）插入一个数据元素ListInsert（&L，i，e）
（9）删除数据元素ListDelete（&L，i，&e）

**2.1.3线性表的知识结构**
略 （后期补充）

### 2.2线性表的顺序存储结构
**2.2.1顺序存储结构**
```cpp
typedef struct
{
	ElemType data[MaxSize];
	int length;
}SqList;
//逻辑位序和物理位序差1
//逻辑位序 + 1 = 物理位序
```

**2.2.2顺序表运算的实现**
1、建立顺序表
```cpp
void CreateList(SqList *&L,ElemType a[],int n)
{
	int i;
	L=(SqList *)malloc(sizeof(SqList)); //给L分配一块连续的内存空间
	for(i=0;i<n;i++)
		L->data[i]=a[i];
	L->length=n;
}
```
①顺序表指针的含义
②顺序表指针引用
--引用参数将执行结果回传给参数
--引用符号“&”放在形参L的前面
--输出型参数均为使用“&”，不论参数值是否改变

2、
（1）初始化线性表InitList（L）
```cpp
void InitList(SqList *&L)
{
	L=(SqList *)malloc(sizeof(SqList));
	L->length=0;
}
```

（2）销毁线性表DestroyList（L）
```cpp
void DestroyList(SqList *&L)
{
	free(L); //释放了L所指的空间
}
```

(3)判定是否为空表ListEmpty（L）
```cpp
bool ListEmpty(SqList *L)
{
	return(L->length==0);
}
```

(4)求线性表的长度ListLength(L)
```cpp
int ListLength(SqList *L)
{
	return L->length;
}
```

(5)输出线性表DispList（L）
```cpp
void DispList(SqList *L)
{
	if(ListEmpty(L))return ;
	for(int i=0;i<L->length;i++)
	{
		cout<<L->data[i]<<endl;
	}
}
```
(6)求某个数据元素值GetElem(L,i,e)
```cpp
bool GetElem(SqList *L,int i,ElemType &e)
{
	if(i<1||i>L->length)return false;
	e=L->data[i-1];
	return true;
}
```

(7)按元素值查找LocateElem（L，e）
```cpp
int LocateElem(SqList *L,ElemType e)
{
	int i=0;
	while(i<L->length&&L->data[i]!=e)
		i++;
	if(i>=L->length)return 0;
	else return i+1;
}
```

(8)插入数据元素ListInsert(L,i,e)
```cpp
bool ListInsert(SqList *&L,int i,ElemType e)
{
	if(i<1||i>=L->length) return false;
	i--;//将逻辑序号转换成物理序号
	for(int j=L->length;j>i;j--)
		L->data[j]=L->data[j-1];
	L->data[i]=e;
	L->length++;
	return true;
}
```

(9)删除数据元素ListDelete(L,i,e)
```cpp
bool ListDelete(SqList *&L,int i,ElemType &e)
{
	if(i<1||i>=L->length) return false;
	e=L->data[i];
	for(int j=i;j<=L->length-1;j++)
		L->data[j]=L->data[j+1];
	L->length--;
	return true;
}
```
**2.2.3顺序表算法设计**
例：已知长度为n的线性表A采用顺序存储结构。设计一个时间复杂度为O（n），空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
以下两种方法都不满足要求：
	①如果每删一个值为x的元素都进行移动，其时间复杂度为O（n^2）,空间复杂度为O（1）。
	②如果借助一个新的顺序表，存放将A中所有不为x的元素，其时间复杂度为O（n），空间复杂度为O（n）。
```cpp 
解法一：（重建法）设删除A中所有值等于x元素后的顺序表为A1，显然A1包含在A中，为此A1中重用A的空间。
	思路：扫描顺序表A，重建A只包含不等于x的元素。

void double(SqList *&A,ElemType x)
{
	int k=0;
	for(int i=0;i<A->length;i++)
	{
		A->data[k]=A->data[i];
		k++;
	}
	A->length=k;
}

解法二：（前移法）用k记录顺序表A中等于x的元素个数，一边描述A一边统计k值。
	思路：将不为x的元素前移k个位置(相当于覆盖了为x的位置），最后修改A的长度。

void delnode(SqList *&A,ElemType x)
{
	int k=0;
	while(i<A->length)
	{
		if(A->data[i]==x)
			k++;
		else A->data[i-k]=A->data[i];
	}
	A->length-=k;
}
```
例：假设有两个集合A和B分别用两个线性表LA和LB表示，即线性表中的数据元素即为集合中的成员。编写一个算法求一个新的集合C=A∪B，即将两个集合的并集放在线性表LC中。
```cpp
解题思路：①LC<-LA ②LC<-LB中不在LA中的元素
void unionList(List LA,List Lb,List &LC)
{
	int lena,i;
	ElemType e;
	InitList(LC);
	for(int i=1;i<=ListLength(LA);i++)
	{
		GetElem(LA,i,e);
		ListInsert(LC,i,e);
	}
	lena=ListLength(LA);
	for(int i=1;i<=ListLength(LB);i++)
	{
		GetElem(LB,i,e);
		if(!LocateElem(LA,e))
			ListInsert(LC,++lena,e);
	}
}
```

例：设顺序表L有10个整数。设计一个算法，以第一个元素为分界线（基准），将所有小于等于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。

```cpp
解法一：（前后交换法）
void move(SqList *&L)
{
	int i=0,j=L->length-1;
	ElemType tmp;
	ElemType pivot=L->data[0];
	while(i<j)
	{
		while(i<j&&L->data[j]>pivot)
			j--;
		while(i<j&&L->data[i]<=pivot)
			i++;
		if(i<j){
			tmp=L->data[i];
			L->data[i]=L->data[j];
			L->data[j]=tmp;
		}
	}
	tmp=L->data[0];
	L->data[0]=L->data[j];
	L->data[j]=tmp;
}
```

```cpp
解法二：
void move(SqList *&L)
{
	int i=0,j=L->length-1;
	ElemType pivot=L->data[0];
	while(i<j)
	{
		while(j>i&&L->data[j]>pivot)
			j--;
		L->data[i]=L->data[j];
		while(i<j&&L->data[i]<=pivot)
			i++;
		L->data[j]=L->data[i];
	}
	L->data[i]=pivot;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

空安

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C++代码）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

空安---《数据结构》第二章之上

评论区

精彩推荐

模拟计算器（Java代码）

printf基础练习2 （C语言代码）

假币问题（C++代码）（向上取整的一种处理方式）

IP判断（C++代码）

C语言训练-委派任务* （C语言代码）..................竟然是第一个

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

不容易系列2 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

IP判断（C语言代码）

空安

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C++代码）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

空安---《数据结构》第二章之上

评论区

精彩推荐

模拟计算器 （Java代码）

printf基础练习2 （C语言代码）

假币问题 （C++代码）（向上取整的一种处理方式）

IP判断 （C++代码）

C语言训练-委派任务* （C语言代码）..................竟然是第一个

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

不容易系列2 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

IP判断 （C语言代码）

用筛法求之N内的素数。（C语言代码）

　　评论区

模拟计算器（Java代码）

假币问题（C++代码）（向上取整的一种处理方式）

IP判断（C++代码）

IP判断（C语言代码）