数据结构
- 逻辑结构、物理结构
- 时间复杂度、空间复杂度
线性表
顺序表
#define MAX_SIZE 100
typedef int ElemType;
typedef struct seqlist{
ElemType data[MAX_SIZE];
int length;
}SeqList
//初始化
SeqList* L->data = (SeqList*)malloc(sizeof(Elemtype)*MAX_SIZE);
//查找
int FindByValue(SeqList* L, int e){
int i;
for(i=0;i<L->length;i++){
if(L->data[i] == e)
return i+1;
}
return -1;
}
//插入
bool ListInsert(SeqList*L, int i, int e){
if(i<1 || i>L->length+1) return false;
if(L->length >= MAX_SIZE) return false;
for(int j = L->length;j>=i;j--){
L->data[j] = L->data[j-1];
}
L->data[i-1] = e;
L->length++;
return true;
}
//删除
bool ListDelete(SeqList*L, int i, int* e){
if(L->length == 0) return false;
if(i<1 || i>L->length) return false;
e = L->data[i-1];
for(int j=i;j<L->length;j++){
L->data[j-1] = L->data[j];
}
L->length--;
return true;
}
1.编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C，已知顺序表A和B的元素个数分别为m和n。其中顺序表采用动态分配空间，定义如下。
Typedef struct{
Elemtype * elem; //存储空间基地址
int length; //当前长度
int listsize； //当前分配的存储容量
}SeqList;
算法思想：【双指针不回溯】
要合并两个有序的顺序表A和B，那么需要开辟一个新的数组空间C，当A和B都未到末尾时，挨个比较A和B的元素，将小元素放入到C中，当元素相等时，只保留一个。当A或B结束时，将未结束表的元素逐个放入到C中。
void Combination（SeqList &L1，SeqList &L2， SeqList &L3）{
int i=0,j=0,k=0;
while((i!=L1->length)&&(j!=L2->length){
if(L1->data[i]>L2->data[j]){
L3->data[k++]=L2->data[j++];//L1中元素大，合并L2中元素到L3中
}
else if(L1->data[i]==L2->data[j]){
L3->data[k++]=L2->data[j++];//元素相等，只保留一个，合并到L3中
i++；
}
else{
L3->data[k++]=L1->data[i++];//L2中元素大，合并L1中元素到L3中
}
L3->length++;
}
while(i<L1->length){ //L2结束，合并L1中的元素到L3中
L3->data[k++]=L1->data[i++];
L3->length++;
}
while(j<L2->length){ //L1结束，合并L2中的元素到L3中
L3->data[k++]=L2->data[j++];
L3->length++;
}
}
2.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,a3,...,an-1,an）->(an,an-1,...,a3,a2,a1)。
算法思想：【逆置】要实现数组的逆置，且要求使用原有空间，只需要将对应的数组元素位置交换就可以，如第1个(对应下标是0)和第n个(对应下标是n-1)交换，第2个(对应下标是1)和第n-1个(对应下标是n-2)交换，需要交换的连个元素的下标之和是n-1,其中n是表长。
int ListOppose(SeqList &L){
int i;
ElemType x;
//只需要遍历原表的一半就可以实现数据元素位置的交换
for(i=0; i<L->length/2; i++){
x = L->data[i];
L->data[i] = L->data[L->length-i-1]; //数据元素交换 -> 逆置
L->data[L->length-i-1]=x;
}
return 1；
}
3.一个线性表中的元素全部为正或负整数，试设计一算法，再尽可能少的时间内重排该表，将正、负整数分开，使线性表中所有负整数在正整数前面。
算法思想：【快速排序】
算法中提出暂存的第一个元素不作为比较的标准，比较的标准是0，判断对应的元素是否是正数或者负数。
int ReArrange(SeqList &a, int n){
int low=0,high=n-1;
int t=a[low]; //枢轴元素，只是暂存，不作为比较对象
while(low<high){
while(low<high&&a[high]>=0) //寻找小于0的元素
high--;
a[low]=a[high];
while(low<high&&a[low]<0) //寻找大于0的元素
low++;
a[high]=a[low];
}
a[low]=t; //将枢轴元素放到最终位置
return 1；
}
4.已知线性表（a1,a2,a3,...,an-1,an）按顺序结构存储且每个元素为不相等的整数。设计把所有奇数移到所有偶数前边的算法(要求时间最少，辅助空间最少)
算法思想：【快排】
通过对数字模2是否等于0进行判断，使得奇数元素都在左边，偶数元素都在右边。
具体方法：设置两个指针变量分别指向表头和表尾，它们分别向中间移动，指向表头的数组指针如果遇到偶数且指向标为的数组指针遇到奇数，则互相交换，然后继续移动直至两者相遇。
void part(int arry[], int n){
int i,j.temp;
i=0,j=n-1;
while(i<j){
while(i<j&&array[i]%2 != 0) //i指针从前往后扫描数组，遇到偶数停下
i++;
while(i<j&&array[j]%2 == 0) //j指针从后往前扫描数组，遇到奇数停下
j--;
if(i<j){ //如果i<j,交换两个指针分别指向的元素
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
5.已知在一维数组A[1,...,m+n+1]中依次存放着连个顺序表：（a1,a2,a3,...,am）和（b1,b2,b3,...,an）。试编写程序，将数组中凉饿顺序表的位置互换，即将（b1,b2,b3,...,an）放在（a1,a2,a3,...,am）的前面。
算法思想：
第一步：将A中所有元素逆置，变成bn,bn-1,...,b1,am,am-1,...,a1。
第二步：将前n个逆置
第三步：将后m个逆置
void Reserve(ElemType A[], int left, int right, int arraySize){
if(left>=right || right>=arraySize)
return;
int mid =(left+right)/2;
for(int i=0; i<=mid-left; i++){
ElemType temp = A[left+i];
A[left+i] = A[right-i];
A[right-i] = temp;
}
}
void Exchange(ElemType A[], int m, int n, int arraySize){
Reserve(A,0,m+n-1,arraySize);
Reserve(A,0,n-1,arraySize);
Reserve(A,n,m+n-1,arraySize);
}
6.设有一个线性表存放在一维数组a[0,...,n-1]中，编程将数组中每个元素循环右移k位，要求只用一个辅助单元，时间复杂度为O(n)。
void Reserve(int* array, int p, int q){
for(; p<q; p++,q--){
int temp = array[q];
array[q] = array[p];
array[p] = temp;
}
}
void RightShift(int* array, int n, int k){
k%=n;
Reserve(array,0,n-1);
Reserve(array,0,n-1-k);
Reserve(array,n-k,n-1);
}
单链表
typedef struct LNode{
ElemType data;
struct LNode* next;
}LNode, *LinkList;
//结点创建
LNode *p;
p=(LNode*) malloc(sizeof(LNode));
p->data = 20;
p->next = NULL;
//添加q
q->next = p->next;
p->next = q;
//删除p的直接后继
q=p->next;
p-next =q->next;
free(q);
-
头插法 单链表逆序 头指针（不是数据结点）
-
尾插法 单链表顺序 尾指针（数据结点）
//头插法LinkList Creat_list(LinkList head){
head = (LinkList)malloc(sizeof(LNode)); //为头指针开辟内存空间
LNode *node = NULL; //定义工作指针
head->next = NULL;
node = head->next; //将最后一个结点的指针域永远保持为NULLint count=0; //创建结点的个数 scanf("%d", &count); for(int i=0; i<count; i++){ node = (LNode*)malloc(sizeof(LNode)); //为新结点开辟内存空间 node->data = i; //为新结点的数据域赋值 node->next = head->next;//将头指针所指向的下一个结点的地址，赋值个新创建的结点的next head->next = node; //将新创建的结点的地址赋值个头指针的下一个结点 } return head;}
//尾插法
LinkList Creat_list(LinkList head){
head = (LinkList)malloc(sizeof(LNode)); //为头指针开辟内存空间
LNode *node = NULL; //定义工作指针
LNode *end = NULL; //定义尾指针
head->next = NULL; //初始化头结点知道的下一个地址为NULL
end = head; //未创建其余结点之前，只有一个头结点int count=0; //创建结点的个数 scanf("%d", &count); for(int i=0; i<count; i++){ node = (LNode*)malloc(sizeof(LNode)); //为新结点开辟内存空间 node->data = i; //为新结点的数据域赋值 end->next = node; //新结点赋值给end的下一个 end = node; //新结点成为新的尾结点 } end->next = NULL; return head;}
//查找
bool GetElem_L(LinkList &L, int i, ElemType &e){
//L为带头结点的单链表的头指针
//当第i个元素存在时，其值赋值给e并返回true，否则返回false
LNode *p = L->next;
int j = 1;
while(p && j<i){
p = p->next;
++j;
}
if(!p || j>i) return false;
e = p->data;
return true;
}LNode Locate_Node(LNode L, int key){
/ 在以L为头结点的单链表中查找值为key的第一个结点/
LNode * p = L->next; //p指向第一个数据结点
while(p!=NULL && p->data != key)
p = p->next;if(p->data == data) return p; else{ printf("No Result.\n"); return NULL; }}
//插入
bool ListInsert_L(LinkList &L, int i, ElemType e){
//在带头结点的单链线性表L中第i个位置之前插入元素e
LNode *p = L;
int j=0;
while(p && j<i-1){ //寻找第i-1个结点的位置的过程
p = p->next;
++j;
} //寻找第i-1个结点
if(!p ||j>i-1) return false;//执行插入操作 LNode *s； s=(LinkList)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return true;}
//删除
bool ListDelete_L(LinkList &L, int i, ElemType &e){
//在带头结点的单链表L中，删除第i个元素，并由e返回其值
LNode *p;
LNode *q;
p=L;
int j=0;
while(p->next && j<i-1){ // 寻找第i个结点，并令p指向其前驱
p = p->next;
++j;
}
if(!(p->next) || j>i-1) return false; //删除位置不合理
q=p->next;
p->next = q->next; //删除并释放结点
e=q->data;
free(q);
return true;
}void Delete_LinkList(LNode *L, int key){
//删除以L为头结点的单链表中值为key的第一个结点
LNode *p = L, *q=L->next;
while(q!=NULL && q->data!=key){
p=q;
q=q->next;
}
if(q->data == key){
p->next = q->next;
free(q);
}
else printf("NULL\n");
}//从头到尾依次遍历，输出各个元素的值
void printL(LinkList L){
LNode *p;
p=L->next;
while(p!=NULL){
printf("%d ",p->data);
p=p->next;
}
}
1.给定键值按升序排列的带头结点的单链表La和Lb,将其合并成升序排列的单链表，并返回新链表的表头指针。要求利用原表的结点数据空间。
算法分析：若La、Lb两个链表的长度分别为m,n,则合并链表的时间复杂度为O(m+n)。
LNode *Merge_LinkList(LNode *La, LNode *Lb){
//合并以La和Lb为头结点的两个有序链表
LNode *Lc，*pa,*pb,*pc,*ptr;
Lc=La;
pc=La;
pa=La->next;
pc=Lb->next;
whlile(pa!=NULL && pb!=NULL){
if(pa->data < pb->data){ //将pa所指的结点合并，pa指向下一个结点
pc->next = pa;
pc=pa;
pa=pa->next;
}
if(pa->data > pb->data){ //将pb所指的结点合并，pb指向下一个结点
pc->next = pb;
pc=pb;
pb=pb->next;
}
if(pa->data == pb->data){ //将pb所指的结点合并，pb所指结点删除
pc->next = pa;
pc=pa;
pa=pa->next;
ptr=pb;
pb=pb->next;
free(ptr);
}
if(pa!=NULL) //将剩余结点链接上
pc->next = pa;
else
pc->next = pb;
free(Lb);
return Lc;
}
}
2.删除单链表中所有值重复的结点，使得所有结点的值都不相同
基本思想：从单链表的第一个结点开始，对每个结点进行检查，检查链表中的结点的所有后继结点，只要有结点的值和该结点的值相同，就删除；然后检查下一个结点，直到所有的结点都检查过。
void Delte_Node_vale(LNode *L){ //时间复杂度O(n2) 空间复杂度O(1)
//删除以L为头结点的单链表中所有值相同的结点
LNode *p=L->next, *q, *ptr; //q是被删除结点的直接前驱 ptr是被删除元素
while(p!=NULL){
q=p;
ptr=p->next;
//检查结点p的所有后继结点ptr
while(ptr!=NULL){
if(ptr->data == p->data){
q->next = ptr->next;
free(ptr);
ptr=q->next;
}
else{
q=ptr;
ptr=ptr->next;
}
}
p=p->next;
}
}
//其他方法：借助Hash，用空间换时间
3.试写出逆转线性单链表的算法，单链表结点的类型定义如下
typedef struct node{
ElemType data;
struct node* next;
}LNode,*LinkList;
基本思想：采用头插法，以此借助原有结点的存储空间建立新的单链表
LNode *revert_list(LNode* head){
if(NULL == head)
return head;
LNode *p = head->next;
head->next = NULL;
LNode *tmp = NULL;
while(p){
tmp = p->next;
p->next = head->next; //头插法
head->next = p;
p=tmp;
}
return head;
}