顺序表和链表基础操作的复习

顺序表

#include<iostream>
using namespace std;
静态
//#define MAX_SIZE 50
//typedef int ElemType;
//typedef struct
//{
//	int length;
//	ElemType nums[MAX_SIZE];
//}Sqlist;
//动态:
#define Init_SIZE 50
typedef int ElemType;
typedef struct
{int length;int maxsize;ElemType* nums;
}Sqlist;
bool ListInsert(Sqlist& l, int i, ElemType e)//在第i个位置插入元素e
{if (i<1 || i>l.length + 1) return false;for (int j = l.length; j >= i; --j)l.nums[j - 1] = l.nums[j];l.nums[i - 1] = e;return true;
}
bool ListInsert(Sqlist& l, int i, ElemType& e)//删除第二个位置的元素
{if (i<1 || i>l.length) return false;ElemType tmp = e;for (int j = i; j < l.length; ++j){l.nums[i - 1] = l.nums[i];}l.length--;return true;
}
//按值查找
int LocateElem(Sqlist& l, ElemType& e)//查找e是第几个位置的元素
{for (int i = 0; i < l.length; ++i){if (l.nums[i] == e) return i + 1;}return -1;
}
//按位查找
int GetElem(Sqlist& l, int i)//返回第i个位置的元素
{if (i<1 || i>l.length) return -1;return l.nums[i - 1];
}
bool Merge(Sqlist A, Sqlist B, Sqlist& C)
{if (A.length + B.length > C.maxsize) return false;int i = 0, j = 0, k = 0;while (i < A.length && j < B.length){if (A.nums[i] < B.nums[j]) C.nums[k++] = A.nums[i++];else C.nums[k++] = B.nums[j++];}while(i<A.length) C.nums[k++] = A.nums[i++];while(j<B.length) C.nums[k++] = B.nums[j++];C.length = k;return true;
}
//int main()
//{
//
//	return 0;
//}

链表

#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct LNode
{ElemType x;struct LNode* next;
}ListNode,*LinkList;
//按位查找
LinkList getElem(LinkList l, int i)//带头链表按序号查找结点值
{int j = 1;LinkList p = l->next;if (i == 0) return p;if (i < 0) return nullptr;while (j < i&&p){p = p->next;j++;}if (p) return p;else return nullptr;
}
//按值查找
LinkList LocateElem(LinkList l, ElemType e)
{LinkList p = l->next;while (p&&p->x!=e){p = p->next;}return p;
}
//插入
//后插
void InsertBack(LinkList l, ElemType e, int i)
{LinkList p = getElem(l, i - 1);LinkList s;s->x = e;s->next = NULL;s->next = p->next;p->next = s;
}
//前插
void InsertFront(LinkList l, ElemType& e, int i)
{LinkList p = getElem(l, i - 1);LinkList s;s->x = e;s->next = NULL;s->next = p->next;p->next = s;ElemType ret = e;swap(p->x, s->x);
}
//删除
void Erase(LinkList l, ElemType& e, int i)
{LinkList p = getElem(l, i - 1);LinkList q = p->next;p->next = q->next;free(p);
}typedef struct DNode
{ElemType x;struct DNode* next,*prev;
}DListNode, * DLinkList;
DLinkList getElem(DLinkList l, int i)//带头链表按序号查找结点值
{int j = 1;DLinkList p = l->next;if (i == 0) return p;if (i < 0) return nullptr;while (j < i && p){p = p->next;j++;}if (p) return p;else return nullptr;
}
void Insert(DLinkList l, int i, ElemType& e)
{DLinkList p = getElem(l, i - 1);DLinkList s;s->x = e;s->next = p->next;s->prev = p;p->next->prev = s;p->next = s;
}