#include<stdio.h>
#include<stdbool.h>
#define MaxSize 50
//顺序表SqList
typedef struct {
int data[MaxSize];
int length;
} SqList;
//初始化空表
void InitList(SqList *L) {
L->length = 0;//这里L是结构体指针，用L->访问成员
}
bool ListInsert(SqList *L,int i,int e) { //按位插入，i是位置，e是插入值
if(L->length==MaxSize) {//表已满
return false;
}
if(i>L->length+1||i<=0) {//不能留空位
return false;
}
if(i==L->length + 1) {//正好插在最后一个元素后面
L->data[i-1]=e;
L->length++;
}
else {
int j=0;
for(j=L->length; j>=i; j--) {//注意j是从后往前走
L->data[j]=L->data[j-1];
}
L->data[i-1]=e;//插入位置只和i有关
L->length++;
}
return true;
}
bool ListDelete(SqList *L,int i,int *e) { //按位删除
if(i<=0||i>L->length) {
return false;
}
*e=L->data[i-1];//e是指针，*e是指针所指的内容，这里要修改指针指向的具体值
int j=0;
for(j=i; j<L->length; j++) {//当j==L->length时直接删掉最后元素，只需L->length--
L->data[j-1]=L->data[j];
}
L->length--;
return true;
}
void PrintList(const SqList *L) { //保护指针L指向的内容，使其为只读，L本身可以改、指向别的
int i=0;
for(i=0; i<L->length; i++) {
printf("%d ", L->data[i]);
}
printf("\n");
}
int LocateElem(const SqList *L,int e) {//打印出来的值无法用变量接收，所以才有数值返回类型
int i=0;
for(i=0; i<L->length; i++) {
if(L->data[i]==e) {
return i+1;
}
}
return 0;
}
void ReverseList(SqList *L) {//表的逆序
int left=0;
int right=L->length-1;
int temp=0;
while(left<right) {
temp=L->data[left];
L->data[left]=L->data[right];
L->data[right]=temp;
left++;
right--;
}
}
void DelAllX(SqList *L,int x) { //删除表中所有＝x的元素，快慢指针法，快指针便历，慢指针记录保留元素
int fast=0;
int slow=0;
while(fast<L->length) {
if(L->data[fast]!=x) {
L->data[slow++]=L->data[fast++];
}
else {
fast++;
}
}
L->length=slow;
}
void EvenFront(SqList *L) { //所有偶数挪到前面，奇数挪到后面，even有偶数的意思
int left=0;
int right=L->length-1;
int temp=0;
while(left<right) {
while(L->data[left]%2==0&&left<right) { //是偶数，并且left<right，left就右移，否则停住
left++;
}
while(L->data[right]%2==1&&left<right) {//是奇数，并且left<right,right就左移，否则停住
right--;
}
if(left<right) {
temp=L->data[left];
L->data[left]=L->data[right];
L->data[right]=temp;
left++;
right--;
}
}
}
bool MergeList(SqList *L1,SqList *L2,SqList *L3) { //将两个有序表合并为一个有序表
if((L1->length+L2->length)>MaxSize) {
return false;
}
int i=0;
int j=0;
int k=0;
while(i<L1->length&&j<L2->length) {
if(L1->data[i]<L2->data[j]) {
L3->data[k++]=L1->data[i++];
}
else {
L3->data[k++]=L2->data[j++];
}
}
while(i<L1->length) {//L1有剩余，直接粘贴到L3
L3->data[k++]=L1->data[i++];
}
while(j<L2->length) {//L2有剩余，直接粘贴到L3
L3->data[k++]=L2->data[j++];
}
L3->length=k;//k就是L3的最终长度,无论去不去重都是，而L1和L2的长度之和就不行了
return true;
}
void DelSame(SqList *L) { //递增有序表删除重复元素，快慢指针法
if(L->length<=1) {//只有一个元素或者空表无需去重
return;//因为DelSame是void，没有要返回的，所以要直接return；
}
int fast=1;
int slow=1;
while(fast<L->length) {//这里注意slow初始值对应元素个数，因为data[0]时slow=length=1
if(L->data[fast]!=L->data[slow-1]) {
L->data[slow++]=L->data[fast];
}
fast++;
}
L->length=slow;
}
void DelSamePlus(SqList *L) { //无序表删除重复元素，快慢指针法
if(L->length<=1) {//只有一个元素或者空表无需去重
return;//因为DelSamePlus是void，没有要返回的，所以要直接return；
}
int fast=1;
int slow=1;
while(fast<L->length) {//fast=length会越界
int i=0;
while(i<slow) {
if(L->data[fast]==L->data[i]) {
break;
}
i++;
}
if(i==slow) {
L->data[slow]=L->data[fast];
slow++;
}
fast++;
}
L->length=slow;
}
void Test() {
SqList L;
printf("----------测试InitList-----------\n");
InitList(&L);//&是取地址，传给指针形参
printf("打印空表长度%d\n",L.length);//这里L是结构体实体，用L.访问成员
printf("----------测试ListInsert-----------\n");
for(int i=0; i<MaxSize; i++) {
ListInsert(&L,i+1,i);
}
printf("----------测试PrintList-----------\n");
PrintList(&L);
printf("----------测试ReverseList-----------\n");
ReverseList(&L);
PrintList(&L);
printf("----------测试DeleteList-----------\n");
int e;
for(int i=0; i<10; i++) {
ListDelete(&L,i+1,&e);
}
PrintList(&L);
printf("----------测试LocateElem-----------\n");
int p=LocateElem(&L,15);
if(p!=0) {
printf("所查元素在第%d位\n",p);
} else {
printf("未找到所查元素\n");
}
printf("----------测试DelAllX-----------\n");
DelAllX(&L,6);
PrintList(&L);
printf("----------测试EvenFront-----------\n");
EvenFront(&L);
PrintList(&L);
printf("-----------测试MergeList-----------\n");
SqList L1,L2,L3;
InitList(&L1);
for(int i=0; i<10; i++) {
ListInsert(&L1,i+1,2*i+1);
}
InitList(&L2);
for(int i=0; i<10; i++) {
ListInsert(&L2,i+1,2*i);
}
InitList(&L3);
PrintList(&L1);
PrintList(&L2);
PrintList(&L3);
MergeList(&L1,&L2,&L3);
PrintList(&L3);
printf("-----------测试DelSame-----------\n");
SqList L4;
InitList(&L4);
ListInsert(&L4,1,1);
ListInsert(&L4,2,1);
ListInsert(&L4,3,2);
ListInsert(&L4,4,2);
ListInsert(&L4,5,2);
ListInsert(&L4,6,4);
ListInsert(&L4,7,4);
ListInsert(&L4,8,6);
ListInsert(&L4,9,7);
ListInsert(&L4,10,8);
PrintList(&L4);
DelSame(&L4);
PrintList(&L4);
printf("-----------测试DelSamePlus-----------\n");
SqList L5;
InitList(&L5);
ListInsert(&L5,1,1);
ListInsert(&L5,2,3);
ListInsert(&L5,3,1);
ListInsert(&L5,4,4);
ListInsert(&L5,5,3);
ListInsert(&L5,6,2);
ListInsert(&L5,7,4);
ListInsert(&L5,8,6);
ListInsert(&L5,9,4);
ListInsert(&L5,10,5);
PrintList(&L5);
DelSamePlus(&L5);
PrintList(&L5);
}
int main(void) {
Test();
return 0;
}
