//在顺序表的第p个位置上插入新的元素e。如果p输入不正确,返回0,p输入正确,插入成功,返回1。 intinsertElem(Sqlist &L, int p, int e) { int i; if(p<0||p>L.length||L.length==maxSize) return0; for(i=L.length-1;i>=p;--i) { L.data[i+1] = L.data[i]; } L.data[p] = e; ++L.length; return1; }
平均移动次数是 n/2
删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14
//删除表L中下标为p的元素,成功返回1,否则返回0,并将被删除元素的值赋给e。 intdeleteElem(Sqlist &L, int p, int &e) { int i; if (p<0||p>L.length-1) return0; e = L.data[p]; for(i=p;i<L.length-1;++i) { L.data[i] = L.data[i+1]; } --L.length; return1; }
单链表
每个结点除了存放数据元素外,还要存储指向下一个节点的指针
定义
1 2 3 4 5 6
//链表的定义 typedefstructNode { int data; structNode* next; }Node, *LinkList;
//链表的创建 //头插法,将新加入的元素都插到表头中 LinkList LinkListCreatH(){ Node* L; L = (Node*)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表 int m; printf("您要创建长度为多少的链表:"); scanf_s("%d", &m); for (int i = 0; i < m; i++) {
int x; //x为链表数据域中的数据 scanf_s("%d", &x);
Node* p; p = (Node*)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->NULL L->next = p; } return L; } //尾插法,将新加入的元素都插入到表尾中 LinkList LinkListCreatT() { Node* L; L = (Node*)malloc(sizeof(Node)); L->next = NULL; int m; printf("您要创建长度为多少的链表:"); scanf_s("%d", &m); Node* s; s = L; // 设置一个和头结点相同起点的的尾巴指针 for (int i = 0; i < m; i++) {
int x; //x为链表数据域中的数据 scanf_s("%d", &x);
Node* p; p = (Node*)malloc(sizeof(Node)); //申请新的结点
//链表的插入 LinkList LinkedListInsert(LinkList L, int i, int x){ Node* pre; //pre为前驱结点 pre = L; // pre 首先指向头结点 int tempi = 0; for (tempi = 1; tempi < i; tempi++) { pre = pre->next; //查找第i个位置的前驱结点 } Node* p; //插入的结点为p p = (Node*)malloc(sizeof(Node)); // 为插入的结点初始化内存 p->data = x; // 为数据域赋值 p->next = pre->next; pre->next = p;
return L; }
删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
//链表的删除 LinkList LinkedListDelete(LinkList L, int x) { Node* p; Node* pre; //pre为前驱结点,p为查找的结点。 pre = (Node*)malloc(sizeof(Node)); // 为插入的结点初始化内存 p = L->next; while (p->data != x) { //查找值为x的元素 pre = p; p = p->next; } pre->next = p->next; //删除操作,将其前驱next指向其后继。 free(p); return L; }
双链表
在单链表的基础上,增加了指向前驱结点的指针
定义
1 2 3 4 5 6
typedefstructDoubleNode { int data; structDoubleNode* prior; structDoubleNode* next; }Dnode,*DnodeList;